Advanced · Module 14
Patterns: two pointers, sliding window, prefix sums
Reusable techniques that turn quadratic loops into linear ones.
Some techniques come up so often that recognizing them is half of solving a problem. This module collects four: converging two pointers on sorted data, the sliding window over contiguous ranges, prefix sums that answer range questions in constant time, and sorting intervals and sweeping through their events. Each turns a quadratic search into a linear or near-linear pass, and each comes with a precise condition for when it applies.
- 1Two pointersPro — members onlyOn a sorted array, two indexes moving toward each other can find pairs with a given sum in one pass, because every move rules out a whole row of candidate pairs. The same argument powers three-sum, container problems and trapping rain water.14 min
- 2Sliding windowPro — members onlyA window over a contiguous range grows on the right and shrinks on the left, with both ends only ever moving forward. Keeping a summary of the window up to date turns many O(n²) substring and subarray searches into O(n).15 min
- 3Prefix sumsPro — members onlyStore the running total at every position once, and the sum of any range becomes one subtraction. Combined with a hash map, prefix sums count subarrays with a given sum, even with negative numbers.14 min
- 4Intervals and sweepingPro — members onlySort intervals by start and most interval problems become a single pass: merging overlaps, inserting a new interval, or sweeping through start and end events to count how many intervals overlap at once.14 min