Unit 2 · Highest leverage
The four patterns that solve a disproportionate share of problems. Recognising which one applies is worth more than any amount of implementation speed.
What a strong answer looks like
A strong Unit 2 answer names the pattern and states what property of the input makes it valid.
Know
Precomputing cumulative totals turns any range-sum query into a single subtraction, trading linear setup for constant queries.
Apply
Use prefix sums when many range queries will be asked of unchanging data.
Watch out
Rebuilding the prefix array after every update, which erases the benefit on changing data.
Study move
Answer three range-sum queries from one prefix array.
Know
Two indices moving toward or with each other exploit sortedness or a monotonic property to avoid checking every pair.
Apply
Move the pointer that makes progress toward the target, and justify why that direction is safe.
Watch out
Applying two pointers to unsorted data where the monotonic property does not hold.
Study move
Find a pair summing to a target in a sorted array and justify each pointer move.
Know
A window over a contiguous range grows and shrinks to maintain a property, giving linear time where nested loops would be quadratic.
Apply
Define the window property first, then decide what forces the left edge forward.
Watch out
Resetting the window on a violation instead of advancing the left edge, which discards the linear behavior.
Study move
Find the longest substring without repeats and state what moves the left edge.
Know
Binary search applies to any monotonic predicate, not only to sorted arrays, which is what lets it search an answer space.
Apply
Identify the monotonic property, then binary search on the answer rather than the data.
Watch out
Restricting binary search to literal sorted arrays and missing the more powerful use.
Study move
Frame a minimisation problem as a binary search over candidate answers.
Connections and techniques that receive extra attention in this unit.
Related topics some schools attach to this unit and others leave out. Covered on request rather than assumed.
Modeling drill
Given many range-sum queries on fixed data and one problem asking for the longest valid window, state which technique fits each and why.
