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: C++
Interval Problems in C++: One Sort, One Sweep, and a Heap When You Need It
Interval problems look like a family of tricks. They are one trick applied seven ways, and the trick fits in a sentence: sort by start time, and every question about overlap becomes a question about the element you just looked at. Without the sort, “do any two of these overlap?” is a pairwise check over n² pairs. With it, an interval can only overlap the ones immediately around it, so one linear walk answers the question. Three of the seven problems below need nothing more than that walk. The other four need one extra structure — a heap — and READ MORE
Sorting in C++: Five Algorithms, Stability, and What the Merge Step Buys You
Almost nobody implements a sorting algorithm at work. You call std::sort and move on. So the usual defence of learning them — “it builds fundamentals” — is doing a lot of unpaid labour in that sentence. Here is a better reason, and it is the one this post is built on. Three of the five algorithms below contain a reusable subroutine that shows up as LeetCode problems in its own right. Merge sort’s merge step is a problem. Quicksort’s partition step is four problems. And one character inside merge sort decides whether the algorithm is stable, which changes what you READ MORE
Binary Search on the Answer in C++: Five Problems With Nothing to Search
Nobody stores an array of eating speeds. There is no sorted list of ship capacities. And yet both problems are binary search, and recognising that is the single highest-leverage thing in this whole series — because once you see it, a large family of “find the minimum X such that Y” problems stops being a family and becomes one template. This is the third of three posts on Joseph Choi’s binary search session deck. Part one covered the ten problems where a sorted array supplies the predicate; part two removed the sorting and replaced it with local comparisons and reference READ MORE
Binary Search Without a Sorted Array: Peaks and Rotations in C++
Every binary search in part one had a sorted array underneath it. Take that away and most people assume the technique goes with it. It does not — sortedness was never the requirement, only the most convenient way to meet it. This is the second of three posts on Joseph Choi’s binary search session deck. Seven problems here, in two families: three where the array rises and then falls, and four where a sorted array has been rotated. In both, something other than the sort order tells you which half to keep. As in part one, every listing was compiled READ MORE
Binary Search in C++: The Boundary Template and 10 Sorted-Array Problems
Binary search is the algorithm everyone knows and almost nobody writes correctly on the first try. The reason is not the idea, which is two lines. It is that every failure mode is silent: no crash, no timeout, just a wrong index. This is the first of three posts working through Joseph Choi’s binary search session deck in C++. Between them they cover twenty-two LeetCode problems, and they are split by the only question that matters — where does the monotonicity come from? This post takes the ten problems where it comes from the sort order, and sets up the READ MORE
LeetCode Queue Design Patterns in C++: Put the Answer at an Edge
LeetCode Queue Design Patterns in C++: Put the Answer at an Edge LeetCode Queue Design Patterns in C++: Put the Answer at an Edge nycomdorics.com · preview of the WordPress post · source deck by Joseph Choi A binary heap will hand you its smallest element instantly and tell you nothing whatsoever about the second smallest. A std::vector will append and remove at the back in constant time and charge you a full shift to remove from the front. Every structure in this family is generous at its edges and useless in its interior. So the design job is always READ MORE
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
Prefix Sum in C++: Nine LeetCode Problems and One Equation
Prefix sum on LeetCode is one equation wearing nine costumes. Once you write down that the sum of a slice equals one running total minus another, every problem below turns into a question about what to store and what to look up. Nine of them are here: 1480, 303, 304, 560, 974, 325, 1524, 525, and 523. 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 nine problems at a glance # Problem Difficulty Family 1480 Running Sum of 1d Array Easy Build the READ MORE
Cycle Sort in C++: Six LeetCode Array Problems That Are the Same Problem
Cycle sort on LeetCode is the pattern behind a group of array problems that look unrelated on the problem list and turn out to be the same eight lines of C++ with a different last paragraph. Six of them are below: 268, 448, 287, 645, 442, and 41. If you can write the skeleton from memory, you can solve all six, and the Hard one stops being a Hard. 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 six problems at a glance # READ MORE