TechPrep

Searching and ordering

Binary search (including on the answer), monotonic stacks, interval sweeps and heaps.

Lessons

  1. 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.
  2. 02Monotonic stackKeep a stack whose values only decrease (or increase) so each element finds its next greater or smaller neighbour in one pass.
  3. 03Intervals: sort, then sweepSort by start (or end) so overlaps become adjacent, then sweep once while comparing only with the last interval kept.
  4. 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.