Sorting an array to answer a question about it is often the wrong move, and this post is about the two ways to notice. The first: sometimes you do not need the array sorted, only partly sorted. Quicksort’s partition step puts one element in its final place and separates everything else into two sides — and if all you want is the k-th largest, that single step is enough, and repeating it is O(n) rather than O(n log n). Four problems below are that idea. The second: sometimes you do want it sorted, and then sorted order pays you back READ MORE
Tag: two pointers
Decrease and Conquer in C++: Twelve LeetCode Problems That Throw the Search Space Away
Decrease and conquer on LeetCode is the habit of proving that a whole block of candidates cannot possibly hold the answer, and then deleting it without looking. Twelve problems here run on that one move: 167, 11, 42, 121, 53, 1014, 169, 240, 277, 280, plus two that are worth including precisely because one of them isn’t this pattern at all and the other should be. All the code here compiles and runs against the sample cases plus the edge cases listed at the bottom. More problems: the LeetCode series. The twelve problems at a glance # Problem Difficulty Shape READ MORE