Searching and ordering
Binary search (including on the answer), monotonic stacks, interval sweeps and heaps.
Lessons
- 01Binary search, including on the answerHalve a search space whose predicate flips once from false to true, whether the space is an array or a range of possible answers.
- 02Monotonic stackKeep a stack whose values only decrease (or increase) so each element finds its next greater or smaller neighbour in one pass.
- 03Intervals: sort, then sweepSort by start (or end) so overlaps become adjacent, then sweep once while comparing only with the last interval kept.
- 04Heaps and top-KA size-K min-heap keeps the K largest items seen so far; its top is the answer and everything smaller is discarded.