Array scanning patterns — turning a nested loop into a single pass
Code that walks an array with a nested loop becomes noticeably slow past about 10,000 items. That's 100 million iterations.
At this point, the patterns for rewriting aren't that many. Depending on the problem's nature, one of four hits. Knowing the patterns lets you look at slow code and immediately judge "this can be one pass".
What you'll learn in this chapter
- Two-pointer — walk a sorted array from both ends inward
- Sliding window — slide a contiguous range, reusing previous work
- Prefix sum — precompute so range totals cost
O(1) - Monotonic stack — find "next greater element" in one pass
- Decision procedure for picking the pattern when you see slow code
Builds on "watch for hidden loops" from Complexity. Also uses stacks from Choosing data structures.
The shared idea
The four patterns share one thing. Replace the waste of the inner loop starting from scratch every time with reuse of previous results.
The "hash to drop O(n²) to O(n)" from the Complexity chapter is the same family. That one was "remember what you've seen in a set". The four here use the order or contiguity of the array — that's the difference.
Two-pointer — walk from both ends
From a sorted array, find two elements summing to a target. Naive is O(n²).
Mark both ends and move left rightward when the sum is small, right leftward when it's large.
function twoSumSorted(xs: number[], target: number): [number, number] | null {
let lo = 0;
let hi = xs.length - 1;
while (lo < hi) {
const sum = xs[lo] + xs[hi];
if (sum === target) return [xs[lo], xs[hi]];
if (sum < target) lo++; // want a larger sum
else hi--; // want a smaller sum
}
return null;
}
console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 10)); // [ 4, 6 ]
console.log(twoSumSorted([1, 3, 4, 6, 8, 11], 100)); // null
lo and hi only converge, so the walk ends in n steps total. O(n).
The correctness basis is "we never need to look at a dropped pair again". When the sum is under target, lo's only chance is a larger partner. But hi is currently the maximum, so lo can't reach with anyone. So lo can be dropped whole.
Applicability condition: sorted. Using it on unsorted arrays misses answers. If unsorted, first consider a hash-based method. Sorting costs O(n log n), so as seen in the Recursion and divide-and-conquer chapter, the whole thing bounds there.
Sliding window — slide a contiguous range
Fixed length
"What is the largest sum of 3 contiguous items?" Recomputing per range is O(n × k).
Sliding by one changes only the one leaving and the one entering.
function maxWindowSum(xs: number[], k: number): number {
let sum = 0;
for (let i = 0; i < k; i++) sum += xs[i];
let best = sum;
for (let i = k; i < xs.length; i++) {
sum += xs[i] - xs[i - k]; // add the entering one, subtract the leaving one
if (sum > best) best = sum;
}
return best;
}
console.log(maxWindowSum([2, 1, 5, 1, 3, 2], 3)); // 9
Updating only the diff gives O(n).
Variable length
If the window width isn't fixed, advance the right end and shrink the left while conditions hold.
function minWindowLen(xs: number[], target: number): number {
let lo = 0;
let sum = 0;
let best = Infinity;
for (let hi = 0; hi < xs.length; hi++) {
sum += xs[hi];
while (sum >= target) { // while condition holds, shrink left for the shortest
best = Math.min(best, hi - lo + 1);
sum -= xs[lo++];
}
}
return best === Infinity ? 0 : best;
}
console.log(minWindowLen([2, 3, 1, 2, 4, 3], 7)); // 2
The inner while looks like a nested loop, but lo doesn't decrease, so it advances at most n times total. Combined O(n).
Applicability: as the range grows and shrinks, the condition changes monotonically. In the example above, all elements are positive, so growing the range monotonically grows the sum. If negatives mix, that monotonicity breaks and you can't judge whether to shrink left.
Prefix sum — precompute range totals
If range totals are asked repeatedly, precompute "cumulative sum from the head".
function buildPrefix(xs: number[]): number[] {
const p = new Array<number>(xs.length + 1).fill(0);
for (let i = 0; i < xs.length; i++) p[i + 1] = p[i] + xs[i];
return p;
}
const xs = [4, 2, 7, 1, 9, 3];
const prefix = buildPrefix(xs);
const rangeSum = (l: number, r: number): number => prefix[r + 1] - prefix[l];
console.log(`sum of [1,3] = ${rangeSum(1, 3)}`); // sum of [1,3] = 10
console.log(`sum of [0,5] = ${rangeSum(0, 5)}`); // sum of [0,5] = 26
Precompute O(n); each subsequent query O(1). q queries total O(n + q) versus O(n × q) for recomputing each time — the more queries, the more the gap widens.
The implementation key is placing 0 at the head. With p[0] = 0, no case split is needed even when l is 0. Boundary case splits breed bugs; this one cell removes it.
Element updates require rebuilding. Fits reads-heavy, updates-light. Frequent updates need another data structure.
Monotonic stack — "next greater element"
For each element, find "the first element to the right of self that's greater than self". Naive is O(n²).
Stack the elements whose answer isn't decided yet.
function nextGreater(ys: number[]): number[] {
const out = new Array<number>(ys.length).fill(-1);
const stack: number[] = []; // indices. Corresponding values are non-increasing bottom to top
for (let i = 0; i < ys.length; i++) {
while (stack.length > 0 && ys[stack[stack.length - 1]] < ys[i]) {
out[stack.pop() as number] = ys[i]; // the stacked element's answer is decided now
}
stack.push(i);
}
return out;
}
console.log(nextGreater([2, 1, 5, 3, 6, 4]).join(","));
// 5,5,6,6,-1,-1
2 and 1 both answer 5; 5 and 3 both answer 6; 6 and 4 have no greater to the right, so -1.
Each element is stacked once and popped once — even with the inner while, the total is O(n).
The stack staying monotonic (non-increasing bottom-to-top here) is the source of the name. When a new element arrives, elements smaller than it can be popped ("answer now decided"). Never looking at a popped element again is the O(n) justification.
This pattern is the foundation for problems like "the largest rectangle inside a bar chart" or "how much rainwater is trapped" — finding taller walls on left and right.
Decision procedure
Find an O(n²) nested loop and apply in this order.
| What the inner loop is doing | Applicable pattern | Applicability condition |
|---|---|---|
| Finding "the value paired with this value" | Hash (unsorted) / Two-pointer (sorted) | Two-pointer requires sorted |
| Redoing aggregation of a contiguous range | Sliding window | Condition changes monotonically as range grows/shrinks |
| Asking for range totals many times | Prefix sum | Element updates are rare |
| Finding "first element greater/smaller than self" | Monotonic stack | Answer settles from a one-direction walk |
First check "is the inner loop starting from scratch every time". If it is, there's room to reuse prior results. If not (e.g., truly enumerating all pairs), the output is already O(n²) so it can't be reduced.
Sometimes none apply. In that case, confirm whether O(n²) is even a problem at your item count. At 100 items it's 10,000 iterations — not worth optimizing.
Common misconceptions
"Inner while means nested loop." — Count total walk operations. Variable-length windows and monotonic stacks stay O(n) because the total inner work is bounded by n. Count per-element touches, not loop appearances.
"Two-pointer works if you sort first." — Sorting costs O(n log n), canceling the O(n) benefit. Hash is the default for unsorted. Sort only when the order itself is part of the answer.
"Prefix sum is always fast." — Every update requires an O(n) rebuild. Choose by read/update ratio.
"Learn the patterns and you can apply them." — Applicability conditions are the essence. Variable-length window needs monotonicity, two-pointer needs sorted, monotonic stack needs one-direction settling. Applying without checking silently gives wrong answers.
Exercises
Q1. From access logs, "the largest count in a contiguous 5-minute range" for a day (~80,000 items) takes tens of seconds. How to fix?
Answer and explanation
Answer: Use a sliding window. Cutting by time rather than by count makes it variable-length.
The slow implementation probably counts "the 5 minutes starting here" from scratch per time. With k items per range, O(n × k).
Sliding by one changes only the item leaving and the item entering. Updating only the diff gives O(n).
Watch the boundary. Cutting the window by count (not time) overshoots during sparse periods: 5 minutes holds fewer items than the count you chose, so a fixed-count window stretches past 5 minutes. Cut by time, and drop from the left anything older than "right end − 5 minutes" — a variable-length form is accurate. This form also stays O(n) because lo doesn't go back.
Precondition: logs must be in time order. If not, an initial sort at O(n log n) is required.
Q2. Given a price array, "for each product, the price of the first higher-priced product to its right". Naive is a nested loop. How to reduce?
Answer and explanation
Answer: Monotonic stack for O(n).
Stack the indices of products whose answer isn't decided. When you see a new price, pop off the top for as long as it's "cheaper than the current price", setting its answer to the current price.
Each product is stacked once and popped once. Even with the inner while, the total is 2n, so O(n).
The stack stays monotonic — that's why it works. The pop condition is "cheaper than the current price", so what remains is always at least the current price — cheaper going up. This property lets you stop and not look at the rest.
The same shape finds "the first higher-priced product to the left" — just reverse the walk direction. Combining both gives "the range between higher-priced products", useful for price-band analysis.
Q3. Two-pointer to "find two elements summing to a target" didn't find the answer in some cases. What to check?
Answer and explanation
Answer: Check whether the array is sorted.
Two-pointer's basis is: "when sum is under target, left can't reach anyone, so drop it". That judgment depends on right being the current maximum. If not sorted, right isn't the max, so the "drop it" conclusion doesn't follow.
Verify with a line asserting input is ascending. Common shapes: descending order, or partially sorted.
Unsorted → use hash. Walk once and ask "is (target − current) already seen" — O(n) without sorting. Sorting just to use two-pointer becomes O(n log n) and is slower.
Choose two-pointer only when input is already sorted. Data from the database with ORDER BY, or time-ordered logs, fit.
Summary
- The shared idea of the four patterns: replace the inner loop's re-work with reuse of prior results
- Two-pointer — walk from both ends.
O(n). Sorted required - Sliding window — update only the delta of enter/leave. Variable-length requires monotonic condition change with range
- Prefix sum — precompute
O(n), thenO(1)per query. Fits few updates. Placing 0 at the head removes boundary case splits - Monotonic stack — each element stacked once, popped once, so
O(n). Never look at popped elements again is the basis - Inner
whiledoesn't necessarily mean nested loop. Count by total walk operations - Hash is the default for unsorted. Sorting just for two-pointer bounds the whole thing at
O(n log n) - Applicability conditions are the essence, not the patterns. Apply without checking → silent wrong answers
O(n²)is fine at ~100 items. Confirm the count before reducing
- Complexity — "Watch for hidden loops" is the starting point for this chapter
- Indexes — Same "precompute for faster reads" trade-off, on the database side
What to read next
- Capacity estimation — On to Part 11. From counting steps inside one machine, to designs that span multiple
- Indexes — See the precomputation vs. update-cost trade from the database's side
- Choosing data structures — Which structure speeds up which operation