Two Pointers
Why two pointers exists — the story
You've been asked a version of Two Sum on a sorted array: return the pair of indices whose values add up to a target. It sounds trivial. Your first idea is the honest one — try every pair, keep the winners.
The obvious way: two nested loops. For every index i, walk every index j > i and check if a[i] + a[j] == target. Correct. Simple. Roughly n·(n-1)/2 comparisons.
For a 1,000-element array that's about 500,000 comparisons — a millisecond. Nobody complains. And it's not a stupid approach: the O(n²) loop is what almost every textbook writes first, and for n < 500 you'd need a stopwatch to notice a difference. If interviews stopped at n = 1,000, we could all go home.
But the interviewer says n = 10⁶. Now the naive scan is 5 × 10¹¹ comparisons — roughly 8 minutes on a modern CPU. Your interviewer will not wait 8 minutes. And here's what stings: the array is sorted, and you're using none of that order. Every one of those 500 billion comparisons is throwing information away.
The pattern is the fix. Two pointers walk the array from opposite ends (or the same end, at different speeds). Every step, one of them moves — and each move eliminates all pairs involving the value you just left behind. You never revisit. You never backtrack. One sweep. O(n).
The core idea — sweep from both ends, discard whole batches
Set left = 0, right = n - 1. Compare a[left] + a[right] to the target:
- Sum too big? The value at
rightis the culprit — anything paired witha[right]will also be too big, becausea[right]is the largest remaining element and every possible partner (all indices fromlefttoright-1) is at leasta[left]. Soright--discardsn - left - 1untested pairs in one move. - Sum too small? Symmetric.
a[left]is too small to complete any pair with the remaining candidates. Soleft++. - Sum equal? Return the pair.
Every iteration moves one pointer, so the total work is bounded by right - left, which starts at n-1 and shrinks to zero. That's O(n) time, O(1) extra space. Compared to the O(n²) brute force at n = 10⁶, we went from 8 minutes to about 1 millisecond — a half-million-times speedup for four lines of code.
The invariant that makes this correct is subtle and worth naming aloud in an interview: at every step, the pair we skipped could not have summed to the target. If you cannot state that invariant, you don't understand the pattern yet — go back and re-read the paragraph above.
When to use it — recognition signals
Reach for two pointers when the problem has any of the following shapes:
- A sorted array (or something you can sort cheaply — usually
n log nsort +nsweep still beatsn²) and you're looking for a pair, triple, or quadruple with a sum / difference / product property. - A palindrome check — compare
leftandright, move inward until they meet. - Partitioning in place — move all zeros to the end, sort by parity, Dutch National Flag (three-way partition using three pointers).
- Merging two sorted sequences without allocating a new array (
merge-sorted-array, "merge intervals" preparation). - Container / area / volume problems where the answer depends on two boundary indices — Container With Most Water, Trapping Rain Water.
- "Remove duplicates in place" patterns — one pointer reads, the other writes.
- "Squared / absolute value" transformations on a sorted array — the extremes are the largest, so you fill the answer from the back.
If you catch yourself writing for i in range(n): for j in range(i+1, n): on a sorted or sortable input, stop. Two pointers is almost certainly the O(n) fix.
When NOT to use it
Two pointers is the wrong hammer if:
- The input is unsorted and sorting would destroy information — for example, if you need original indices in the answer and the sort would lose them. (Fix: pair each value with its index before sorting; or use hashing instead.)
- You need every valid pair, not one. Two pointers finds one pair per
O(n)sweep. If the answer requires enumerating all pairs (e.g., "count all pairs with sum ≤ target"), you may need to combine two pointers with counting, or reach for a different tool entirely. - The problem is about subarrays with a size or sum constraint — that's Sliding Window, not two pointers. Two pointers is about pair selection; sliding window is about contiguous range accumulation. Confusing the two is the single most common interview trap in this family.
- The array is small and the interviewer is testing your data-structure knowledge — e.g., "given an unsorted array of
n ≤ 100integers, find any pair summing tok". Here a HashMap-based O(n) solution shows more range than a sort-then-sweep. - You need lookups by value while pointing — a HashMap is the right tool. Two pointers only compares the values under the current pointers, never arbitrary elements.
- The data structure is a stream or a linked list without random access — pointer arithmetic requires O(1) index access; on a singly-linked list, only the Fast/Slow variant applies.
The templates
Java 17. The comments explain why each line exists, not what it does — you already know what a while loop does.
Opposite-end template (sorted array, find pair)
int[] twoSumSorted(int[] a, int target) {
int left = 0, right = a.length - 1; // start at extremes; every pair (l,r) with l<r is reachable
while (left < right) { // < not <=: we never pair an index with itself
int sum = a[left] + a[right];
if (sum == target) return new int[]{left, right};
if (sum < target) left++; // a[left] too small — no pair involving a[left] can hit target
else right--; // a[right] too big — symmetric
}
return new int[]{-1, -1}; // no pair exists
}Why it terminates: right - left strictly decreases each iteration. Bounded by n-1 initial gap → O(n) iterations. Why the answer is correct: the invariant "if a pair exists, it lies within [left, right]" holds at every step, because each move only discards pairs proven infeasible.
Same-end template (in-place partition / dedup)
int removeDuplicates(int[] a) {
if (a.length == 0) return 0;
int write = 1; // slow pointer: next slot to write a unique value
for (int read = 1; read < a.length; read++) { // fast pointer: scanning input
if (a[read] != a[read - 1]) { // new value found?
a[write++] = a[read]; // yes — record it, advance write
}
// else: skip; write stays put, effectively overwriting the duplicate later
}
return write; // length of deduped prefix
}Invariant: a[0..write) is the deduped prefix at every step; everything at index ≥ write is scratch we're allowed to overwrite. Why one pass suffices: each element is read once, written at most once.
Three-way partition template (Dutch National Flag)
void sortColors(int[] a) { // values ∈ {0, 1, 2}
int lo = 0, mid = 0, hi = a.length - 1;
while (mid <= hi) { // three pointers: two writers + one reader
if (a[mid] == 0) swap(a, lo++, mid++); // 0 goes to lo region; mid safe to advance
else if (a[mid] == 2) swap(a, mid, hi--); // 2 goes to hi region; DON'T advance mid — swapped-in value is unknown
else mid++; // 1: already in the middle band
}
}
static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }Invariant: a[0..lo) are all 0s, a[lo..mid) are all 1s, a[mid..hi] are unknown, a[hi+1..n) are all 2s. Trap: when you swap a 2 out, you have no idea what came back — that's why mid does not advance in the a[mid] == 2 branch.
Complexity summary
| Template | Time | Space | Notes |
|---|---|---|---|
| Opposite-end (pair sum) | O(n) | O(1) | Requires sorted input; O(n log n) if you must sort first |
| Same-end (partition / dedup) | O(n) | O(1) | Single pass, in-place |
| Three-way partition | O(n) | O(1) | Only when the value domain is small (2–3 categories) |
For pair / triple / quadruple sum problems: k-Sum reduces to (k-1)-Sum + one two-pointer sweep, so 3Sum is O(n²), 4Sum is O(n³), etc. Sort once; use nested loops fixing k-2 values; use two pointers for the innermost pair.
Traps & gotchas — the 5 that fail candidates on interview day
When you find a valid triple in 3Sum, the next iteration must skip over identical values or you'll emit [1, 1, 2] twice for input [1, 1, 2, 2]. Not skipping is the number-one interview-day bug. Fix: after finding an answer, while (left < right && a[left] == a[left-1]) left++; — apply the same trick to right and to the outer loop's fixed index.
For distinct-index pair-sum, use <. For palindrome checks where a middle character is fine, <= also works but is redundant. Getting this wrong causes the pair (i, i) — pairing an index with itself — to be counted, which quietly fails [3] with target 6.
After you find one pair in 2Sum, the natural instinct is to advance both left++; right--; and keep searching. On distinct-values input this is fine. On input with duplicates ("find all pairs"), this loses the pair (left, right-1) that also might sum correctly. Advance only what's needed; walk both past duplicates explicitly.
The template's correctness proof depends on a[left] being the smallest remaining candidate. If the input is unsorted, left++ no longer means "the next smaller value is gone." Half the interviews I've conducted have candidates confidently apply two pointers to [3, 1, 4, 1, 5, 9, 2, 6] for pair-sum; the algorithm silently returns the wrong answer. Always ask, or sort explicitly.
a[left] + a[right] can overflow int when values are near Integer.MAX_VALUE. Use long accumulation, or write the comparison as a[left] < target - a[right] (safe when both sides fit in int). This is the JDK-Arrays.binarySearch-style trap all over again.
History — Dijkstra's flag, 1976
The three-way partition variant of two pointers has a name: Dutch National Flag. Edsger Dijkstra published it in 1976 as a teaching example — three regions (red, white, blue, in Dutch flag order), swap items until the flag is sorted. It became the canonical pivot step of every modern quicksort implementation, including Java's Arrays.sort on primitive types. The two-index opposite-end pattern is older still, appearing informally in Knuth's Sorting and Searching (1973) as a merge subroutine.
Why does an obscure teaching example matter? Because when you tell an interviewer "I'll use two pointers, specifically the Dutch National Flag partition," you are not just naming a technique — you are quoting a lineage. It signals depth. Nobody with a year of experience knows the name; every staff engineer does.
Canonical problem walkthrough — Container With Most Water
Problem (↗ LeetCode): You have n non-negative heights h[0..n-1] representing vertical lines drawn from the x-axis. Pick two lines that, together with the x-axis, form a container holding the maximum amount of water. Return that maximum area.
Water is capped by the shorter of the two chosen walls, and the width is the horizontal distance between them. So for chosen indices i < j, area = min(h[i], h[j]) · (j - i).
Approach 1 — Brute force (the honest first attempt)
Try every pair. Two nested loops. Track the max.
int maxAreaBrute(int[] h) {
int best = 0;
for (int i = 0; i < h.length; i++) {
for (int j = i + 1; j < h.length; j++) {
int area = Math.min(h[i], h[j]) * (j - i);
if (area > best) best = area;
}
}
return best;
}Complexity: O(n²) time, O(1) space. For n = 10⁵ (a typical LeetCode constraint), that's 10¹⁰ operations — about 3 minutes at 50M ops/sec. The interviewer's smile will fade.
Why is this wasteful? Every pair is inspected, but most pairs are dominated by a shorter width and a shorter minimum height simultaneously. We're computing areas for pairs that can't possibly be optimal.
Approach 2 — The two-pointer sweep (the insight)
Place left = 0, right = n - 1. This is the widest possible container. Any move inward loses width, so it can only pay off if we can find a taller minimum wall to compensate.
The key observation: the container's height is min(h[left], h[right]). Suppose h[left] < h[right]. If we move right inward, the new width is smaller and the height is capped at either h[left] (unchanged) or something smaller (if the new right is shorter than h[left]). Either way, moving right inward when h[left] is the shorter wall cannot improve the area — the shorter wall bottlenecks us.
The only useful move is left++: give up on h[left] (it can't do better than it just did, because we're at the widest possible pairing for it) and hope for a taller left wall.
Symmetric: when h[right] ≤ h[left], move right--.
int maxArea(int[] h) {
int left = 0, right = h.length - 1, best = 0;
while (left < right) {
int area = Math.min(h[left], h[right]) * (right - left);
if (area > best) best = area;
// Discard the shorter wall — its best possible area was just computed
if (h[left] < h[right]) left++;
else right--;
}
return best;
}Complexity: O(n) time, O(1) space. For n = 10⁵, that's 10⁵ operations — about 2 milliseconds. A 150,000× speedup over brute force.
Correctness sketch (the interview one-liner): when we advance left past the shorter wall h[left], we discard every pair (left, k) for k > right. But every such pair had width ≤ right - left and height ≤ h[left] (because h[left] was the shorter wall of the widest such pair), so their area is ≤ the area we just computed. Nothing is lost.
Approach 3 — Micro-optimize the skip
The above is optimal in Big-O, but we can save constant factors: instead of moving one step at a time, skip over walls no taller than the one we just abandoned.
int maxAreaFast(int[] h) {
int left = 0, right = h.length - 1, best = 0;
while (left < right) {
int lo = Math.min(h[left], h[right]);
int area = lo * (right - left);
if (area > best) best = area;
while (left < right && h[left] <= lo) left++; // no shorter wall can improve
while (left < right && h[right] <= lo) right--;
}
return best;
}This helps significantly on inputs with many small walls in a row (e.g., [1,1,1,...,1,100,1,1,...]). It doesn't change asymptotic complexity, but for LeetCode's stricter time budgets and for very "flat" inputs, it can be 2-3× faster in practice.
Complexity ladder
| Approach | Time | Space | When to reach for it |
|---|---|---|---|
| Brute force | O(n²) | O(1) | n ≤ 1000, or as a correctness reference |
| Two-pointer sweep | O(n) | O(1) | Every real interview answer |
| Two-pointer with skip | O(n) | O(1) | Contest programming, or "make it faster" follow-ups |
Interview delivery: state brute force in 15 seconds. Say "we can do O(n) with two pointers because the shorter wall bottlenecks the area, so it's the one to discard." Write the two-pointer version. Mention the skip optimization as a follow-up if time permits.
3Sum Medium
i is fixed, the sorted suffix is a two-sum problem; move left/right until the triple hits zero, then skip duplicates.Problem
Find all unique triplets (a, b, c) in the array with a + b + c = 0. The output must contain no duplicate triplets.
Constraints: 3 ≤ n ≤ 3000; values fit in int; the array is unsorted (you'll sort it first).
Example 1: [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]].
Example 2: [0,0,0,0] → [[0,0,0]] (many duplicates, one unique triplet).
Solution — brute force
Brute force is three nested loops over i < j < k, checking every triplet and putting sorted triplets into a set to avoid duplicates. That is O(n³) time plus output/dedup space, and it times out quickly at n = 3000. Sorting first lets us fix one value and replace the inner pair scan with two pointers, cutting the search to O(n²) while still skipping duplicates deterministically.
List<List<Integer>> threeSumBrute(int[] a) {
Set<List<Integer>> seen = new HashSet<>();
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++)
for (int k = j + 1; k < a.length; k++)
if (a[i] + a[j] + a[k] == 0) {
List<Integer> t = Arrays.asList(a[i], a[j], a[k]);
Collections.sort(t);
seen.add(t);
}
return new ArrayList<>(seen);
}Brute-force cost: O(n³) time plus dedup/output space — too slow for n ≥ 10⁴.
Solution — optimized
Sorting turns the inner two-number search into a monotone two-pointer scan. Fix one pivot, search for its negated complement, and skip equal values so the same triplet is emitted once.
Pattern. Sort, fix one element, converge two pointers for the remaining pair; skip duplicates at every level.
Steps.
- Sort the array — sortedness lets us prune and two-pointer.
- Loop
iover each element as the outer pivot. Skip duplicate pivots:if (i > 0 && a[i] == a[i-1]) continue;. - For each pivot, set
lo = i+1,hi = n-1; hunt pairs summing to-a[i]. - If
s < 0→lo++; ifs > 0→hi--; ifs == 0→ record the triplet. - After a hit, skip duplicates on both pointers before advancing:
while (a[lo]==a[lo+1]) lo++;and mirror forhi. - Break early when
a[i] > 0— no positive triple sums to zero.
Java.
List<List<Integer>> threeSum(int[] a) {
Arrays.sort(a);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < a.length - 2; i++) {
if (i > 0 && a[i] == a[i-1]) continue; // skip dup pivot
if (a[i] > 0) break; // smallest already positive
int lo = i + 1, hi = a.length - 1;
while (lo < hi) {
int s = a[i] + a[lo] + a[hi];
if (s == 0) {
res.add(List.of(a[i], a[lo], a[hi]));
while (lo < hi && a[lo] == a[lo+1]) lo++; // skip dup
while (lo < hi && a[hi] == a[hi-1]) hi--;
lo++; hi--;
} else if (s < 0) lo++;
else hi--;
}
}
return res;
}Time Complexity
Existing summary: Time O(n²) · Space O(1) (excluding output/sort).
Sorting costs O(n log n), then each pivot runs a linear two-pointer scan over the suffix, giving O(n²) total; O(n²) dominates the sort for large n.
Space Complexity
Extra space is O(1) excluding the output and sort implementation, because the algorithm uses only indices and the result list required by the problem.
Learning notes
- Why sort first? — without sorted order,
lo++/hi--cannot safely discard ranges. - Why skip duplicate pivots? — the same first value would generate the same triplets again.
- Why
if (a[i] > 0) break? — after sorting, three positive numbers cannot sum to zero. - Why set
lo = i + 1? — each triplet uses indices after the fixed pivot. - Why skip duplicates after a hit? — equal
loorhivalues would re-emit the same triplet.
For fixed i, [lo,hi] brackets all unexplored pairs summing toward -a[i]; sortedness makes each move monotone.
[-1,0,1,2,-1,-4] sorts to [-4,-1,-1,0,1,2]. Fix -1, then two pointers on the rest find 0+1 and -1+2 → triplets [-1,0,1] and [-1,-1,2].
"I first confirm the output needs unique triplets and the input is unsorted, so sorting is allowed. I start with brute force by checking all triples and deduping them, which is O(n³) time and too slow. I optimize by sorting, fixing one pivot, and two-pointering the remaining pair with duplicate skips for O(n²) time and O(1) extra space excluding output."
Missing any of the three duplicate-skips yields repeated triplets. Example: nums=[-1,-1,-1,2]. Without skipping duplicate pivots you emit [-1,-1,2] twice (once per -1 as pivot); without skipping lo/hi after a hit, [0,0,0,0] emits [0,0,0] multiple times.
Generalizes to k-Sum by recursion (fix outer indices, two-pointer the base case). 4Sum = one more loop.
Common Mistakes
- Missing any of the three duplicate-skips — pivot,
lo,hi. All three are required. - Advancing
lo/hibefore skipping duplicates — do the skip on the value you just consumed, then advance. - Using
longfor the sum unnecessary here (constraints keep it withinint), but confirm when values approach10⁹. - Not sorting first breaks the two-pointer discard argument — the whole approach collapses to O(n³).
Same pattern, new tweaks
Sort once, then let two converging pointers do the work — the target and the counting change, the skeleton doesn't:
| Variation | The one thing that changes | Time |
|---|---|---|
| 3Sum Closest | instead of hunting for exactly 0, track the sum closest to target as the pointers move | — |
| 3Sum Smaller | count triplets with sum < target; when a[lo]+a[hi] < target, all hi−lo pairs qualify at once, so add them in one shot | — |
| 4Sum | add one more outer loop, then two-pointer the inner pair (skip duplicates at every level) | — |
| Triplets with Smaller Sum | same batch-counting trick as 3Sum Smaller | — |
Container With Most Water Medium
↗ LeetCode: Container With Most Water
Problem
Each element is the height of a vertical wall. Pick the two walls that (with the x-axis) hold the most water — area = min(h[i], h[j]) × (j − i).
Constraints: 2 ≤ n ≤ 10⁵; heights ≥ 0.
Example 1: [1,8,6,2,5,4,8,3,7] → 49.
Example 2: [1,1] → 1 (the only pair has width 1 and height 1).
Solution — brute force
Brute force checks every pair of walls (i, j), computes min(h[i], h[j]) * (j - i), and keeps the largest area. It is easy to reason about and uses O(1) space, but it is O(n²) time because there are all-pairs choices. The optimized two-pointer version keeps the widest container first and moves only the shorter wall, because moving the taller wall cannot raise the limiting height.
int maxAreaBrute(int[] h) {
int best = 0;
for (int i = 0; i < h.length; i++)
for (int j = i + 1; j < h.length; j++)
best = Math.max(best, Math.min(h[i], h[j]) * (j - i));
return best;
}Brute-force cost: O(n²) time, O(1) space — too slow for n ≥ 10⁴.
Solution — optimized
Start with the maximum width and greedily discard the shorter wall. Since width only shrinks, the only possible improvement is finding a taller limiting wall on the short side.
Pattern. Converging pointers; move the shorter wall — the only move that can increase area.
Java.
int maxArea(int[] h) {
int l = 0, r = h.length - 1, best = 0;
while (l < r) {
best = Math.max(best, Math.min(h[l], h[r]) * (r - l));
if (h[l] < h[r]) l++; else r--;
}
return best;
}Time Complexity
Existing summary: Time O(n) · Space O(1).
The optimized loop is O(n) because each iteration moves exactly one pointer inward, so there are at most n−1 area checks.
Space Complexity
Space is O(1) because the method stores two pointers and one best area, with no auxiliary arrays.
Learning notes
- Why start at both ends? — that gives the largest possible width first.
- Why
Math.min(h[l], h[r])? — water height is capped by the shorter wall. - Why multiply by
(r - l)? — width is the distance between chosen indices. - Why move the shorter side? — moving the taller side shrinks width without improving the cap.
- Why
while (l < r)? — a container needs two distinct walls.
Area = min(h[l],h[r]) × (r−l). Width shrinks each step, so only raising the limiting height can help; moving the taller wall can never improve.
[1,8,6,2,5,4,8,3,7]. Widest pair 8@idx1 and 7@idx8 give min(8,7)×7 = 49 — the max. Moving the taller side could only shrink width without raising the limiting height.
"I first confirm we need the maximum area from two vertical lines and width is index distance. I start with brute force by testing every pair, which is O(n²) time and O(1) space. I optimize with two pointers at the ends, moving the shorter wall each step, for O(n) time and O(1) space."
Moving the taller wall can never help. Example: heights=[1,8,6,2,5,4,8,3,7], lo=0(h=1), hi=8(h=7). Moving hi inward shrinks width and can't raise the min (already 1). Move the shorter wall — the only move that can improve area.
Greedy converging pointers. Contrast with Trapping Rain Water, which accumulates water rather than maximizing a single span.
Same pattern, new tweaks
Two pointers closing in from the ends, always moving the one that can't hurt you:
| Variation | The one thing that changes | Time |
|---|---|---|
| Trapping Rain Water | instead of maximizing one span, accumulate water per bar using the smaller of the two running maxes | — |
| Valid Palindrome / Valid Palindrome II | compare from both ends inward; II allows one mismatch (try skipping either side) | — |
| Boats to Save People | sort, then pair the lightest with the heaviest that still fits — a converging-pointer greedy | — |
Squaring a Sorted Array Easy
↗ LeetCode: Squares of a Sorted Array
Problem
Given a sorted array that may contain negatives, return the squares of every number, also in sorted order — in O(n).
Constraints: 1 ≤ n ≤ 10⁴; input sorted ascending; negatives allowed (their squares can be the largest).
Example 1: [-4,-1,0,3,10] → [0,1,9,16,100].
Example 2: [-3,-2,-1] → [1,4,9] (all negatives reverse after squaring).
Solution — brute force
Brute force squares every element, then sorts the squared values. That is correct because sorting restores the lost order after negatives become positive, but it costs O(n log n) time and O(n) output space. The sorted input still gives structure: the largest remaining square must be at the left or right end, so the optimized method fills the output array from back to front in one pass.
int[] sortedSquaresBrute(int[] a) {
int[] res = new int[a.length];
for (int i = 0; i < a.length; i++) res[i] = a[i] * a[i];
Arrays.sort(res);
return res;
}Brute-force cost: O(n log n) time, O(n) space for output — slower than the required O(n) pass.
Solution — optimized
Sorted input means the largest absolute value is always at one of the ends. Compare both ends, place the larger square at the back, and shrink the side you used.
Pattern. A sorted array may contain negatives, whose squares are large. Merge from both ends inward — the biggest square is always at one of the two ends.
Java.
int[] sortedSquares(int[] a) {
int n = a.length, left = 0, right = n - 1;
int[] res = new int[n];
for (int pos = n - 1; pos >= 0; pos--) { // fill largest-first, back to front
int ls = a[left] * a[left], rs = a[right] * a[right];
if (ls > rs) { res[pos] = ls; left++; }
else { res[pos] = rs; right--; }
}
return res;
}Time Complexity
Existing summary: Time O(n) · Space O(n) (output).
The optimized pass is O(n) because pos fills exactly n slots and each step consumes either left or right once.
Space Complexity
Space is O(n) for the required output array. Apart from res, the algorithm uses only a few integer pointers.
Learning notes
- Why compare end squares? — the largest remaining square must be at an extreme.
- Why fill from
n - 1downward? — we discover squares largest to smallest. - Why move
left++whenls > rs? — that value has been placed and cannot be reused. - Why
elsefor ties? — either equal square is fine. - Why not square in place and return? — negatives make squared order unsorted.
After squaring, the array is no longer sorted (e.g. [-4,-1,0,3] → [16,1,0,9]). But the largest square must come from the most-negative or most-positive value — i.e. an end. So compare the two ends, take the larger square, and fill the result back to front.
[left, right] still spans every element whose square hasn't been placed; pos marks the next slot to fill from the right, so the output is built in descending square order.
[-4,-1,0,3,10]. Compare ends: (-4)²=16 vs 10²=100 → take 100, then 16, 9, 1, 0; fill the output back-to-front → [0,1,9,16,100].
"I first confirm the input is already sorted but may contain negatives, so squared order can break. I start with brute force by squaring everything and sorting, which is O(n log n) time and O(n) space. I optimize by comparing absolute extremes with two pointers and filling from the end, giving O(n) time and O(n) output space."
Squaring in place, then sorting. Example: nums=[-4,-1,0,3,10] → squared [16,1,0,9,100] still needs a sort (O(n log n)). Two pointers from the ends fill an output array from the back in O(n).
"Merge from both ends because the extreme is at an end" is the same converging-pointer idea as Container With Most Water, and mirrors the merge step of merge sort operating on a fold-point.
Same pattern, new tweaks
| Variation | The one thing that changes | Time |
|---|---|---|
| Sort Transformed Array | after applying ax²+bx+c the extremes are at the ends (if a>0) or middle (if a<0); merge accordingly | — |
| Merge Sorted Array (in place, from the back) | fill from the largest end so you never overwrite unmerged values | — |
| Intersection of Two Arrays II | sort both, then two pointers advancing the smaller side | — |
Sort Colors (Dutch National Flag) Medium
Problem
Sort an array of 0s, 1s, and 2s in place in a single pass (the Dutch-national-flag problem) — no library sort.
Constraints: 1 ≤ n ≤ 300; values ∈ {0,1,2}; O(1) extra space, one pass.
Example 1: [2,0,2,1,1,0] → [0,0,1,1,2,2].
Example 2: [0] → [0] (already sorted single bucket).
Solution — brute force
Brute force can count how many 0s, 1s, and 2s appear, then overwrite the array with that many of each value. That is O(n) time and O(1) space, but it uses two passes; a comparison sort would be O(n log n) and unnecessary. The Dutch National Flag optimization keeps three regions and partitions in one pass, which is the version to present when the interviewer asks for one-pass in-place sorting.
void sortColorsBrute(int[] a) {
int[] cnt = new int[3];
for (int x : a) cnt[x]++;
int idx = 0;
for (int color = 0; color < 3; color++)
while (cnt[color]-- > 0) a[idx++] = color;
}Brute-force cost: O(n) time and O(1) space, but two passes; a library sort is O(n log n). The one-pass requirement motivates Dutch National Flag.
Solution — optimized
The optimized partition keeps three regions: confirmed 0s, confirmed 1s, confirmed 2s, and an unknown middle. Each swap grows one confirmed region without needing a second pass.
Pattern. Three-way partition in one pass with three pointers low, mid, high.
Java.
void sortColors(int[] a) {
int low = 0, mid = 0, high = a.length - 1;
while (mid <= high) {
if (a[mid] == 0) swap(a, low++, mid++);
else if (a[mid] == 1) mid++;
else swap(a, mid, high--); // 2: don't advance mid
}
}
void swap(int[] a, int i, int j){ int t=a[i]; a[i]=a[j]; a[j]=t; }Time Complexity
Existing summary: Time O(n) · Space O(1).
The loop is O(n) because mid moves right or high moves left every iteration, and each element is classified a constant number of times.
Space Complexity
Space is O(1) because sorting happens in-place with three pointers and a constant-size swap temp.
Learning notes
- Why
low,mid,high? — they mark 0-region, unknown-region, and 2-region boundaries. - Why advance both after swapping a 0? — the swapped-in value from
lowis already processed. - Why only
mid++for a 1? — 1 belongs in the middle region. - Why not advance
midafter swapping a 2? — the incoming right-side value is unexamined. - Why
mid <= high? — the unknown region includes both endpoints.
[0,low)=0s, [low,mid)=1s, (high,n)=2s; [mid,high] unprocessed. The three regions only grow.
[2,0,2,1,1,0]. mid walks forward: 0s swap down to low, 2s swap up to high, 1s stay → [0,0,1,1,2,2] in a single sweep.
"I first confirm the only values are 0, 1, and 2 and the array must be sorted in place. I start with brute force as counting buckets or library sort, which is O(n) in two passes or O(n log n) with sort. I optimize with low, mid, and high regions so one scan partitions the array in O(n) time and O(1) space."
Advancing mid after swapping with high skips an unexamined value. Example: [2,0,2], mid=1. Swap a[mid] with a[high] → [2,0,2] (a 2 moves in at mid). If you mid++, you miss re-evaluating that new value. Advance mid only when you swapped with low or saw a 1.
Partitioning is the core of Quickselect/quicksort; the same 3-way scheme handles duplicate-heavy pivots (3-way quicksort).
Same pattern, new tweaks
"Sweep once, swapping items into buckets by category" generalizes the Dutch-flag idea:
| Variation | The one thing that changes | Time |
|---|---|---|
| Move Zeroes | two categories (nonzero vs zero); a single write-pointer packs nonzeros to the front | — |
| Sort Array By Parity | partition into evens then odds with two pointers | — |
| Wiggle Sort | partition around the median, then interleave the two halves | — |
| Partition (Quicksort step) | the same in-place split around a pivot that powers Quickselect | — |
Trapping Rain Water Hard
↗ LeetCode: Trapping Rain Water
Problem
Each bar has width 1; compute how much rain water is trapped between the bars after it rains.
Constraints: 1 ≤ n ≤ 2·10⁴; heights ≥ 0; target O(n) time, O(1) space.
Example 1: [0,1,0,2,1,0,1,3,2,1,2,1] → 6.
Example 2: [4,2,0,3,2,5] → 9 (global side walls matter, not nearest bars).
Solution — brute force
Brute force computes water at each index by scanning left for the tallest wall and scanning right for the tallest wall, then adding min(leftMax, rightMax) - height[i]. That is correct but costs O(n²) time and O(1) space. Precomputing prefix/suffix maxima gives O(n) time with O(n) space; the shown two-pointer version compresses those maxima into two running values for O(1) extra space.
int trapBrute(int[] h) {
int water = 0;
for (int i = 0; i < h.length; i++) {
int leftMax = 0, rightMax = 0;
for (int l = i; l >= 0; l--) leftMax = Math.max(leftMax, h[l]);
for (int r = i; r < h.length; r++) rightMax = Math.max(rightMax, h[r]);
water += Math.min(leftMax, rightMax) - h[i];
}
return water;
}Brute-force cost: O(n²) time, O(1) space — too slow for n ≥ 10⁴.
Solution — optimized
The optimized two-pointer version keeps the best wall seen from each side. Whichever side has the smaller current height can be resolved now, because a sufficient opposite wall exists on the other side.
Pattern. Two pointers tracking leftMax/rightMax; water over a bar is bounded by the smaller side's running max.
Steps.
- Two pointers
lo=0, hi=n-1; carryleftMax = 0,rightMax = 0. - At each step, compare
heights[lo]vsheights[hi]. The shorter side bounds the water. - If
heights[lo] < heights[hi]: ifheights[lo] >= leftMax, updateleftMax; else addleftMax - heights[lo]to the answer. Advancelo++. - Symmetric on the right side: advance
hi--. - Loop until
lo >= hi. Every cell contributes at most once — O(n) time, O(1) space.
Java.
int trap(int[] h) {
int l = 0, r = h.length - 1, lMax = 0, rMax = 0, water = 0;
while (l < r) {
if (h[l] < h[r]) {
lMax = Math.max(lMax, h[l]);
water += lMax - h[l];
l++;
} else {
rMax = Math.max(rMax, h[r]);
water += rMax - h[r];
r--;
}
}
return water;
}Time Complexity
Existing summary: Time O(n) · Space O(1).
The algorithm is O(n) because each iteration moves either l or r inward, so every bar is processed once.
Space Complexity
Space is O(1) because only two pointers, two running maxima, and the water total are stored.
Learning notes
- Why keep
lMaxandrMax? — water depends on the best boundary seen from each side. - Why compare
h[l] < h[r]? — the shorter side is safe to resolve now. - Why update max before adding water? — a new wall traps zero water at itself.
- Why
water += lMax - h[l]? — that is the fill level above the left bar. - Why not use nearest peaks? — trapped water uses global maxima, not local neighbors.
Water above i = min(maxLeft, maxRight) − h[i]. Advance from the side with the smaller max, because that side's bound is fixed regardless of what lies beyond.
If leftMax ≤ rightMax, the water at left depends only on leftMax (a taller-or-equal wall is guaranteed on the right).
[0,1,0,2,1,0,1,3,2,1,2,1] traps 6 units. Over the 0 at index 2, water rises to min(leftMax=1, rightMax=3)=1, so 1 unit sits there; summing every bar gives 6.
"I first confirm each bar has width one and water over a bar depends on the smaller boundary wall. I start with brute force by scanning left and right from every index, which is O(n²) time and O(1) space. I optimize by carrying leftMax and rightMax with two pointers, so each bar is processed once in O(n) time and O(1) space."
Local vs global boundaries. Example: heights=[4,2,0,3,2,5]. Water above index 3 (h=3) is bounded by the global 4 on the left and 5 on the right — not by 3. Track running max from each side (or the shorter side with two pointers).
Also solvable with a monotonic (decreasing) stack that resolves trapped basins between bars — a good cross-check of the two viewpoints.
Common Mistakes
- Local maxima vs global: water above a cell depends on the global bounding walls, not on the nearest peak.
- Wrong side advances: only move the pointer on the shorter side — that's the one whose water level is determined.
- Missing the
>= leftMaxcheck: without it, you subtract onleftMax = heights[lo]and get negative contributions. - Stack-based alternative: also O(n) but uses O(n) space; two-pointer is O(1).
Same pattern, new tweaks
"Water/area is bounded by the smaller enclosing wall" shows up in a few disguises:
| Variation | The one thing that changes | Time |
|---|---|---|
| Container With Most Water | maximize a single span instead of summing trapped water; move the shorter wall | — |
| Trapping Rain Water II (2D) | the "walls" are a whole grid boundary, so process cells outward from the lowest border using a min-heap | — |
| Largest Rectangle in Histogram | the dual "peak" view — a monotonic stack finds how far each bar extends | — |