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
Category: 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
Monotonic Stack Pattern in C++: 13 LeetCode Problems, One Rule for Popping
Thirteen LeetCode problems, three of them rated Hard, and a single sentence that decides all of them. This post works through Joseph Choi’s stack session deck in C++ and tries to answer the question the problem tags never answer: not which data structure, but when does an entry stop being useful? Every solution here was compiled with -fsanitize=undefined,address and checked against a brute-force implementation on tens of thousands of random inputs before it went into the post. Where the deck’s code has a latent trap, I say so and show the version I would submit. The one idea In all 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
LeetCode Linked List Patterns in C++: Recovering the Context a Node Doesn’t Have
A linked list node knows exactly one thing about the world: what comes after it. Not what came before, not how far it is from the end, not whether the walk you started will ever terminate. Every technique in this post exists to recover one of those facts. That is the whole pattern. Array problems start with random access, a length, and a stable index for every element. Linked list problems start with none of that, and the interviewer is testing whether you can rebuild the specific piece you need in one pass and constant space. Once you see a 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