Checkpoint: stacks, search, and intervals
Transfer: five problems you have not seen
One stack, one repair, one answer-space search, and two interval sweeps, with no labels.
Key idea
Added since the last checkpoint
A plain stack, for nesting and for anything where the most recent item resolves first. Augmented stack entries, when a query has to be constant time. A monotonic stack, for nearest-boundary questions. A monotonic deque, when those questions also expire.
Binary search reframed as finding where a property flips, which covers sorted lookups, answer spaces, and arrays with local structure but no global order. The bisect module for when you would rather not write the loop.
Interval sorting by start for connection questions and by end for selection questions, plus the event sweep for anything about how many are active at once.
Tip
One deliberate note
Two of the five below are interval problems and they want different techniques from each other. If you find yourself writing the same loop twice, one of them is wrong.
Simplify Path
Normalize an absolute Unix-style path, resolving . and .. and collapsing repeated slashes. You have written the core of this once already, in a reading rather than as a problem.
Minimum Removals to Balance Parentheses
Remove the fewest parentheses so the string becomes valid, keeping everything else in place. Deciding which ones to remove is the work, and a stack of positions rather than characters is the hint worth taking.
Minimize the Largest Packet
Split a sequence into at most k contiguous groups so that the largest group sum is as small as possible. Write down the candidate range, the feasibility test, and the monotonicity argument before you write any code.
Car Pooling Capacity
Trips each pick up some passengers at one point and drop them at another. Decide whether the vehicle ever exceeds its capacity. The count going up and down by more than one at a time is the only change from what you already know.
Smallest Gap Between Merged Intervals
Merge the overlapping intervals, then report the smallest gap left between consecutive merged blocks. You built both halves of this in a lab.