Two Pointers
Two pointers is the first pattern in this module because it is the smallest idea that produces a real asymptotic win. You hold two indices into one or two sequences, and you move them according to a rule that is cheap to evaluate and provably never discards an answer. The result: a problem that looks like "check all pairs" () becomes a single pass () with no extra memory. Everything else in Module 1 — sliding windows, prefix sums, monotonic deques, the fast/slow pointers of linked lists — reuses the mental model you build here.
Lesson position: Module 1 · Linear Data Structures · previous: Arrays & Strings (overview) · next: Sliding Window · course map.
Why this exists
Many array problems are secretly questions about pairs of positions: which two numbers sum to a target, which two walls hold the most water, where does the "kept" part of an array end and the "discarded" part begin, how do two sorted lists interleave. The naive way to answer a question about pairs is to enumerate all of them. For that is pair checks, which is seconds to minutes in a compiled language and far beyond any interview or contest limit. Two pointers answers the same question with at most pointer moves — for that is steps, a reduction.
The technique has no single inventor; it is folklore that crystallised from three older ideas. The merge step of merge sort (von Neumann, 1945) walks two sorted sequences with one index each. Hoare's partition scheme in Quicksort (1961) converges two indices from the ends of an array toward each other. Dijkstra's Dutch national flag problem (A Discipline of Programming, 1976) is the canonical three-way in-place partition and the canonical example of programming by loop invariant. Competitive programmers later named the family "two pointers" and generalised it to any problem where the rule "move the pointer that cannot possibly be part of a better answer" applies.
You meet two pointers in production more often than you notice. Database engines implement sort-merge joins by walking two sorted inputs in lockstep. Storage engines compact sorted runs (SSTables) by merging them. Unix comm, join and diff on sorted inputs are two-pointer walks. C++'s std::partition, std::unique, std::remove_if, std::merge and std::set_intersection are all two-pointer loops with a standard-library name. The pattern is worth learning rigorously because the same proof technique — a loop invariant that says what has been ruled out — is what keeps those systems correct.
Pattern triggers
Read the problem statement for these literal signals before you touch a keyboard.
| If the problem says or has… | Think of… | Family |
|---|---|---|
| "sorted array" and asks about a pair (sum, difference, product, closest) | Opposite ends converging | A |
| "in place", extra space, "modify the array" | Same-direction read/write | B |
| "remove", "compact", "move all X to the end", "keep the order of the rest" | Same-direction read/write (std::remove_if shape) | B |
| "partition", "sort colors", "three categories", "less / equal / greater than pivot" | Dutch national flag (three pointers) | B |
| "palindrome", "reverse", "symmetric" | Opposite ends converging | A |
| "two sorted arrays/lists" — merge, intersection, union, difference, "is subsequence" | Two sequences | C |
| "container", "area between two lines", "trapped water" | Opposite ends with an exchange argument | A |
| "triplet", "quadruplet", "k numbers that sum to…" | Sort, fix elements, two pointers for the last two | A |
| "linked list" plus "middle", "cycle", "k-th from the end" | Fast/slow pointers (linked lists) | — |
| "contiguous subarray" plus "longest / shortest / count" | Not this page — sliding window | — |
| Unsorted input and you cannot sort (order matters for the answer) | Hash map instead (hash tables) | — |
The last two rows matter as much as the others. A window is a special two-pointer pattern where the two pointers move in the same direction and the thing between them is the object of interest; it has its own page. And if the input is not sorted and sorting would destroy the information you need (for example, you must return original indices), two pointers usually loses to a hash map.
Intuition & first principles
Start with the pair-sum problem on a sorted array: given nums sorted ascending and a target, find indices with nums[i] + nums[j] == target. Picture the grid of all pairs with : the upper triangle. Brute force visits every cell. Two pointers starts at the cell — the top-right corner — and at each step moves one cell down (increase ) or one cell left (decrease ). It visits at most cells of the and still finds the answer. That is only possible because every move eliminates an entire row or column of the grid, and the elimination is justified by sortedness.
Concretely: if nums[lo] + nums[hi] < target, then nums[lo] paired with any nums[j] for is also too small, because nums[j] <= nums[hi]. The entire row is dead. Increment lo. Symmetrically, if the sum is too big, the whole column is dead, so decrement hi. The thing to internalise is not the code but the sentence "the pointer I move can no longer participate in a valid answer". Every two-pointer algorithm is that sentence, specialised.
There are three distinct shapes the sentence takes. Learn them as separate families, because their invariants are different.
flowchart LR
subgraph A["Family A: opposite ends converging"]
A1["lo = 0"] -->|"lo moves right"| A2["..."]
A3["hi = n - 1"] -->|"hi moves left"| A2
end
subgraph B["Family B: same direction read / write"]
B1["write w"] -->|"w trails"| B2["read r"]
B2 -->|"r scans every element once"| B3["n - 1"]
end
subgraph C["Family C: two sequences"]
C1["i walks a[]"] --> C3["compare a[i] vs b[j]"]
C2["j walks b[]"] --> C3
C3 -->|"advance the smaller"| C1
C3 -->|"advance the smaller"| C2
end
Family A — opposite ends converging. Two pointers start at the ends of one array and move toward each other. The loop runs while lo < hi, and each iteration moves exactly one pointer inward. The invariant is about what lies outside [lo, hi]: everything there has been ruled out. Pair sum, container with most water, palindrome check, in-place reverse, 3-sum, trapping rain water.
Family B — same direction, read/write. Both pointers start at the left. A read pointer scans every element exactly once; a write pointer marks the boundary of the output built so far and only advances when something is kept. The invariant is about what lies before the write pointer: it is already the correct output prefix. Remove duplicates, move zeroes, remove_if, Lomuto partition, Dutch national flag (which adds a third pointer at the right end).
Family C — two sequences. One pointer per sequence. At each step you compare the current heads and advance one (or both). The invariant is about what has been consumed: the output so far is the correct answer for the consumed prefixes. Merge two sorted arrays, intersection of sorted arrays, "is subsequence", backspace string compare (which walks two strings backwards).
Fast/slow pointers on linked lists are often listed as a fourth family. They also use two cursors in the same direction, but the argument is about relative speed and the structure is a pointer chain rather than an array, so we treat them in Linked Lists and only summarise them here.
Mechanics
Family A: opposite ends converging
Pair sum in a sorted array
flowchart TD
S["lo = 0, hi = n - 1"] --> C{"lo < hi ?"}
C -->|"no"| N["return not found"]
C -->|"yes"| SUM["s = nums[lo] + nums[hi]"]
SUM --> E{"s == target ?"}
E -->|"yes"| F["return (lo, hi)"]
E -->|"no"| L{"s < target ?"}
L -->|"yes: row lo is dead"| INC["lo = lo + 1"] --> C
L -->|"no: column hi is dead"| DEC["hi = hi - 1"] --> C
Loop invariant (A): at the top of every iteration, every pair with and ( or ) has sum target. Initially lo = 0, hi = n-1, so no pair satisfies the condition and the invariant is vacuously true. Each branch preserves it (proved in Correctness). At exit with lo >= hi, every pair has or , so no pair works. Returning "not found" is therefore correct.
Trace on nums = [1, 2, 4, 7, 11, 15], target = 15 (computed by script):
| Step | lo | hi | nums[lo] | nums[hi] | sum | Decision |
|---|---|---|---|---|---|---|
| 1 | 0 | 5 | 1 | 15 | 16 | too big → hi -= 1 |
| 2 | 0 | 4 | 1 | 11 | 12 | too small → lo += 1 |
| 3 | 1 | 4 | 2 | 11 | 13 | too small → lo += 1 |
| 4 | 2 | 4 | 4 | 11 | 15 | found (2, 4) |
Four steps for candidate pairs. Note that step 1 eliminated the whole column (15 paired with anything is at least 16) and step 2 eliminated the whole row (1 paired with anything remaining is at most 12).
Container with most water
Given heights , maximise . Start with lo = 0, hi = n-1, record the area, then move the pointer at the shorter line. Why is that safe? This is an exchange argument: suppose . Any pair with has width and height , so its area is strictly smaller than the area we just recorded. Every pair that still includes lo is worse than something we already have; lo can retire. The invariant is "the optimal pair is inside [lo, hi], or its area is already recorded in best". On the classic input [1, 8, 6, 2, 5, 4, 8, 3, 7] the answer is 49 (indices 1 and 8: width 7, height 7), and the brute force agrees — verified by script.
When either pointer may move: the pair is recorded, and any pair keeping only one of the two endpoints has a smaller width and no greater height. Moving both at once is also valid but gains nothing.
Valid palindrome and reverse in place
Both are the degenerate case where the rule never depends on the data: always move both pointers. For is_palindrome, compare s[lo] and s[hi], return false on mismatch, else lo += 1, hi -= 1. The invariant is "characters outside [lo, hi] match their mirror images". For "valid palindrome" problems that ignore non-alphanumerics, each pointer first skips characters that do not count — a nested inner loop that still totals because each pointer only moves forward (or backward). For reverse, swap s[lo] and s[hi] and move both; the invariant is "positions outside [lo, hi] hold their final values".
3-sum and 4-sum: sort, fix, then two pointers
To find all distinct triplets summing to zero: sort, then for each i run pair sum on nums[i+1..n-1] with target -nums[i]. Two kinds of duplicate must be suppressed. First, skip i when nums[i] == nums[i-1] — the same first element would regenerate every triplet already found. Second, after recording a triplet at (lo, hi), advance lo past all copies of nums[lo] and retreat hi past all copies of nums[hi]. Both skips are safe because the array is sorted, so equal values are adjacent. On [-1, 0, 1, 2, -1, -4] the sorted array is [-4, -1, -1, 0, 1, 2] and the output is [[-1, -1, 2], [-1, 0, 1]] (verified).
4-sum adds one more outer loop: fix i and j, two-pointer the rest, with the same duplicate skipping at each level. In general, k-sum is after an sort: the outer loops cost and the inner two-pointer pass costs .
Trapping rain water: the two-maxima argument
Water above index equals , where the maxima are taken over and . The three-pass solution computes two prefix-maximum arrays; two pointers computes the same thing in one pass with space. Maintain lmax = max(h[0..lo]) and rmax = max(h[hi..n-1]). If h[lo] < h[hi], settle index lo with lmax; otherwise settle hi with rmax.
Why may we settle lo using only the left maximum when we have not seen the bars between lo and hi? Because we do not need maxRight(lo) exactly — only that it is at least lmax. Invariant: every index already passed on the left was strictly lower than some bar at or beyond the current hi. When lo advanced past index , we had for the hi at that time, and hi only moves left, so is still within h[hi..n-1] and hence . So all of h[0..lo-1] is below maxRight(lo), and h[lo] < h[hi] <= maxRight(lo) as well. Therefore and . The water at lo is exactly lmax - h[lo]. The right side is symmetric. On [0,1,0,2,1,0,1,3,2,1,2,1] both the two-pointer and the prefix-array method return 6 (verified).
Family B: same direction, read/write
Remove duplicates from a sorted array (in place)
w = 1 (the first element is always kept); for r from 1 to n-1, if nums[r] != nums[w-1] then nums[w] = nums[r]; w += 1. Return w. Invariant (B): nums[0..w-1] contains exactly the distinct values of nums[0..r-1], in order, and . Because always, the write never overwrites an element the read has not yet consumed — that is the whole reason the algorithm can be in place.
Move zeroes
Same shape with the predicate "is non-zero": copy every non-zero to nums[w] and advance w; afterwards fill nums[w..n-1] with zeroes. Two passes over the array, still , stable for the non-zero elements. The swap variant (swap nums[r] with nums[w] whenever nums[r] != 0) does it in one pass and is what std::partition's stable cousin std::stable_partition guarantees only with extra memory — stability is free here because every element skipped by w is a zero.
Dutch national flag: three-way partition
Sort an array of values in {0, 1, 2} in one pass with space. Three pointers: lo, mid, hi.
flowchart LR
Z["0 .. lo-1\nall 0"] --> O["lo .. mid-1\nall 1"] --> U["mid .. hi\nunknown"] --> T["hi+1 .. n-1\nall 2"]
Invariant (Dutch flag): a[0..lo-1] are all 0, a[lo..mid-1] are all 1, a[mid..hi] are unexamined, a[hi+1..n-1] are all 2. Initially lo = mid = 0, hi = n-1: the three known regions are empty and the unknown region is the whole array. Loop while mid <= hi and look at a[mid]:
a[mid] == 0: swapa[lo]anda[mid], thenlo += 1, mid += 1. The element that was ata[lo]was a 1 (orlo == midand nothing moved), so it is still in the 1-region.a[mid] == 1:mid += 1. The 1-region grows by one.a[mid] == 2: swapa[mid]anda[hi], thenhi -= 1and do not movemid— the element that arrived froma[hi]is unexamined.
Each iteration shrinks the unknown region by exactly one, so the loop ends after iterations with mid = hi + 1, the unknown region empty, and the three known regions covering the array.
Trace on a = [2, 0, 2, 1, 1, 0] (computed by script; a[mid] is the value before the action):
| Step | a (after) | lo | mid | hi | a[mid] seen | Action |
|---|---|---|---|---|---|---|
| 0 | [2, 0, 2, 1, 1, 0] | 0 | 0 | 5 | — | initial |
| 1 | [0, 0, 2, 1, 1, 2] | 0 | 0 | 4 | 2 | swap(mid, hi), hi -= 1 |
| 2 | [0, 0, 2, 1, 1, 2] | 1 | 1 | 4 | 0 | swap(lo, mid), lo += 1, mid += 1 |
| 3 | [0, 0, 2, 1, 1, 2] | 2 | 2 | 4 | 0 | swap(lo, mid), lo += 1, mid += 1 |
| 4 | [0, 0, 1, 1, 2, 2] | 2 | 2 | 3 | 2 | swap(mid, hi), hi -= 1 |
| 5 | [0, 0, 1, 1, 2, 2] | 2 | 3 | 3 | 1 | mid += 1 |
| 6 | [0, 0, 1, 1, 2, 2] | 2 | 4 | 3 | 1 | mid += 1 → mid > hi, stop |
Six iterations for six elements. Notice step 1: the 2 at mid = 0 is swapped with the 0 at the end, and mid stays at 0 so that the arriving 0 is examined in step 2.
Family C: two sequences
Merge two sorted arrays
i = j = 0; while both have elements, append the smaller head and advance its pointer; then append the rest of whichever remains. Invariant (C): the output holds the smallest elements of in sorted order. When a[i] <= b[j], a[i] is no larger than everything unconsumed in both arrays, so it is the next smallest. Using <= (not <) when taking from a makes the merge stable — equal keys keep a's elements first — which is what merge sort and sort-merge join rely on. LeetCode's variant "merge into a in place from the back" uses the same loop with the pointers starting at the ends, filling from a[m+n-1] downward so nothing is overwritten before it is read.
Intersection of two sorted arrays
Same walk, different action: if a[i] < b[j] advance i; if a[i] > b[j] advance j; if equal, emit and advance both. Each step consumes at least one element, so . Union and set-difference are the same loop with different emit rules; this is exactly std::set_intersection / std::set_union / std::set_difference.
Is subsequence
Is s a subsequence of t? Pointer i into s, j into t. For each t[j], if it equals s[i], advance i. Return i == len(s). The greedy choice — match s[i] to the earliest possible t[j] — is safe by an exchange argument: any embedding that matches s[i] later could be modified to match it earlier without disturbing later matches.
Backspace string compare
Compare two strings typed with # as backspace, in space. Walk both strings from the end, each with a pointer and a pending-skip counter: on # increment the skip counter; on a letter with skips pending, consume a skip; otherwise this is the next live character. Compare the live characters from both sides; mismatch or one side running out early means "not equal". Walking backwards is essential: a # deletes the character before it, so you only know whether a character survives after reading everything to its right.
Fast/slow pointers (briefly)
On a singly linked list you cannot index, but you can run two cursors at different speeds. A slow cursor moving one node per step and a fast cursor moving two finds the middle when fast reaches the end, and detects a cycle when they meet (Floyd's algorithm). Two cursors a fixed distance apart find the -th node from the end in one pass. The proofs — why they must meet inside a cycle, and why resetting one cursor to the head then finds the cycle's start — live in Linked Lists.
The ladder: brute force → better → optimal
Take pair sum as the running example: find indices with nums[i] + nums[j] == target.
Rung 1 — brute force, time, space. Two nested loops over all pairs. Works on any input, sorted or not. For : about additions.
Rung 2 — sort, then binary search each complement, . After sorting (if the input is not already sorted), for each i binary-search for target - nums[i] in nums[i+1..]. searches at each, plus the sort. For : about comparisons for the searches — three orders of magnitude better than rung 1. The improvement comes from replacing the inner linear scan with a logarithmic one; see Searching & Sorting.
Rung 3 — hash set, time, space. One pass: for each x, check whether target - x is already in the set, else insert x. Expected per lookup (Hash Tables), total. Crucially it does not need sorted input and it returns original indices. It pays memory and the constant factor of hashing (a hash computation plus a probe that typically misses cache for large ).
Rung 4 — two pointers on sorted input, time, space. The algorithm above. It needs sorted input; if the input is not sorted, you must spend to sort it first, and then rung 4 is no faster than rung 2 asymptotically — but it is still the right choice for the enumeration problems (all pairs, 3-sum, 4-sum) where the hash approach gets awkward with duplicates.
| Rung | Time | Extra space | Needs sorted? | Returns original indices? | Notes |
|---|---|---|---|---|---|
| Brute force | no | yes | Fine for or so | ||
| Sort + binary search | beyond the sort | sorts first | only if you keep an index map | Dominated by rungs 3/4 | |
| Hash set | expected | no | yes | The right answer for unsorted "two sum" | |
| Two pointers | yes | yes (sorted indices) | The right answer when sorted, or for k-sum |
The honest comparison between rungs 3 and 4 is the one interviewers want to hear: hashing buys independence from order with memory; two pointers buys memory-freedom with order. Neither dominates. For 3-sum, two pointers wins decisively because duplicate handling on a sorted array is two while loops, whereas a hash-based 3-sum needs careful deduplication of triplets.
Correctness
Theorem (pair sum, Family A)
Let nums be sorted ascending. The algorithm returns a pair with the target sum if one exists, and "not found" otherwise.
Invariant : at the start of each iteration, for every pair with : if or then nums[i] + nums[j] != target.
Initialisation. lo = 0, hi = n - 1. No index is below 0 or above , so is vacuous.
Maintenance. Suppose holds and lo < hi. Let $s = $ nums[lo] + nums[hi].
- If $s = $ target, we return
(lo, hi), a correct answer. - If $s < $ target, consider any pair with . If , it is already excluded by . If , sortedness gives
nums[j] <= nums[hi], sonums[lo] + nums[j] <= s < target. Hence every pair with first indexlofails. Afterlo += 1, the new set of pairs with is the old set plus the pairs with $i = $ oldlo, all of which fail. holds. - If $s > $ target, symmetric: any pair with has
nums[i] >= nums[lo], so the sum is $\ge s > $ target. Afterhi -= 1, holds.
Termination. Each iteration either returns or decreases hi - lo by exactly one. Starting from , the loop runs at most iterations.
Exit. When the loop exits with lo >= hi, every pair with has either (if ) or, if , then so . Either way says the pair fails. "Not found" is correct.
The structure of this proof — "the pointer I move cannot be in any undiscovered answer" — transfers to every Family A problem. For container with most water, replace "sum target" with "area best so far" and the maintenance step becomes the exchange argument given earlier.
Dutch national flag (Family B)
Invariant: a[0..lo-1] all 0, a[lo..mid-1] all 1, a[hi+1..n-1] all 2, and the multiset of values is unchanged (we only swap). Each of the three branches was checked above to preserve all three region properties, and each decreases hi - mid by exactly one, so the loop runs exactly times. On exit mid = hi + 1, so the regions [0, lo-1], [lo, mid-1], [mid, n-1] partition the array and the array is sorted.
Merge (Family C)
Invariant: out is sorted and equals the smallest elements of (as a multiset); a[i..] and b[j..] are the remaining elements. When a[i] <= b[j], a[i] is the minimum of all remaining elements, because a and b are each sorted. Appending it keeps out sorted and extends it to the smallest. When one input is exhausted, the other's remainder is exactly the set of elements larger than everything in out, in order.
Complexity
Family A. Each iteration moves one pointer inward by one, and the loop stops when they meet: at most iterations, each , so time in the best, average and worst case (the best case is if the first pair happens to be the answer, but the worst case is what the pattern guarantees). Space . For k-sum: time after sorting. Whether 3-sum can be solved in truly subquadratic time is open; the 3SUM conjecture states it cannot be done in for any , and the best known algorithms shave only polylogarithmic factors off (Grønlund and Pettie, 2014).
Family B. The read pointer visits each element once: exactly iterations, time, space. Dutch flag: exactly iterations as shown. Note that the number of swaps in Dutch flag is at most , but each swap is three memory writes, so on large arrays the constant factor is about that of a stable two-pass approach that writes each element once; measure if it matters.
Family C. Each iteration consumes at least one element from one of the sequences: at most iterations, time. Output size is for merge/union, for intersection.
Constants and cache. All three families read memory sequentially — Family A as two sequential streams moving in opposite directions, Family B as one stream (plus a trailing write), Family C as two forward streams. Hardware prefetchers handle a small number of sequential streams well, so two-pointer loops run near memory bandwidth and are rarely the bottleneck. This is the practical reason sort-merge join is competitive with hash join even though both are after sorting: a hash probe into a table larger than L2 cache is a random access, roughly 100 ns of latency, while a merge step is a predictable sequential read. See How Data Structures Live in Memory.
Implementation
The canonical four: pair sum on a sorted array (Family A), 3-sum with duplicate skipping (Family A, nested), Dutch national flag (Family B) and merge two sorted arrays (Family C). Every block is self-checking with the same test data.
from typing import Optional
def pair_sum_sorted(nums: list[int], target: int) -> Optional[tuple[int, int]]:
"""Indices (lo, hi), lo < hi, with nums[lo] + nums[hi] == target, or None.
Invariant: every pair with i < lo or j > hi has been ruled out."""
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
return (lo, hi)
if s < target:
lo += 1 # row lo is dead: nums[lo] + anything <= s < target
else:
hi -= 1 # column hi is dead
return None
def three_sum(nums: list[int]) -> list[list[int]]:
"""All distinct triplets summing to 0, each sorted, in lexicographic order."""
a = sorted(nums)
n = len(a)
out: list[list[int]] = []
for i in range(n - 2):
if i > 0 and a[i] == a[i - 1]:
continue # same first element -> same triplets
if a[i] > 0:
break # all remaining values positive
lo, hi = i + 1, n - 1
while lo < hi:
s = a[i] + a[lo] + a[hi]
if s < 0:
lo += 1
elif s > 0:
hi -= 1
else:
out.append([a[i], a[lo], a[hi]])
lo += 1
hi -= 1
while lo < hi and a[lo] == a[lo - 1]:
lo += 1 # skip duplicate second elements
while lo < hi and a[hi] == a[hi + 1]:
hi -= 1 # skip duplicate third elements
return out
def dutch_flag(a: list[int]) -> list[int]:
"""In-place 3-way partition of values in {0, 1, 2}.
Invariant: a[:lo] all 0, a[lo:mid] all 1, a[mid:hi+1] unknown, a[hi+1:] all 2."""
lo, mid, hi = 0, 0, len(a) - 1
while mid <= hi:
if a[mid] == 0:
a[lo], a[mid] = a[mid], a[lo]
lo += 1
mid += 1
elif a[mid] == 1:
mid += 1
else:
a[mid], a[hi] = a[hi], a[mid]
hi -= 1 # mid stays: the swapped-in value is unexamined
return a
def merge_sorted(a: list[int], b: list[int]) -> list[int]:
"""Stable merge: on ties, take from a first."""
i = j = 0
out: list[int] = []
while i < len(a) and j < len(b):
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1
out.extend(a[i:])
out.extend(b[j:])
return out
if __name__ == "__main__":
assert pair_sum_sorted([1, 2, 4, 7, 11, 15], 15) == (2, 4)
assert pair_sum_sorted([1, 2, 3], 100) is None
assert pair_sum_sorted([], 5) is None
assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert three_sum([0, 0, 0, 0]) == [[0, 0, 0]]
assert three_sum([1, 2, 3]) == []
assert dutch_flag([2, 0, 2, 1, 1, 0]) == [0, 0, 1, 1, 2, 2]
assert dutch_flag([]) == []
assert dutch_flag([1]) == [1]
assert merge_sorted([1, 3, 5], [2, 4, 6, 8]) == [1, 2, 3, 4, 5, 6, 8]
assert merge_sorted([], [1]) == [1]
assert merge_sorted([2, 2], [2]) == [2, 2, 2]
print("all tests passed")
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class TwoPointers {
/** Indices {lo, hi} with nums[lo] + nums[hi] == target, or null. nums must be sorted. */
static int[] pairSumSorted(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo < hi) {
long sum = (long) nums[lo] + nums[hi]; // long: int + int can overflow
if (sum == target) return new int[]{lo, hi};
if (sum < target) lo++; // row lo is dead
else hi--; // column hi is dead
}
return null;
}
/** All distinct triplets summing to 0, each ascending, in lexicographic order. */
static List<List<Integer>> threeSum(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
List<List<Integer>> out = new ArrayList<>();
for (int i = 0; i + 2 < a.length; i++) {
if (i > 0 && a[i] == a[i - 1]) continue; // same first element
if (a[i] > 0) break; // all remaining positive
int lo = i + 1, hi = a.length - 1;
while (lo < hi) {
long s = (long) a[i] + a[lo] + a[hi];
if (s < 0) lo++;
else if (s > 0) hi--;
else {
out.add(List.of(a[i], a[lo], a[hi]));
lo++;
hi--;
while (lo < hi && a[lo] == a[lo - 1]) lo++;
while (lo < hi && a[hi] == a[hi + 1]) hi--;
}
}
}
return out;
}
/** In-place 3-way partition of values in {0,1,2}: a[0..lo-1]=0, a[lo..mid-1]=1, a[hi+1..]=2. */
static void dutchFlag(int[] a) {
int lo = 0, mid = 0, hi = a.length - 1;
while (mid <= hi) {
if (a[mid] == 0) {
int t = a[lo]; a[lo] = a[mid]; a[mid] = t;
lo++; mid++;
} else if (a[mid] == 1) {
mid++;
} else {
int t = a[mid]; a[mid] = a[hi]; a[hi] = t;
hi--; // mid stays: new a[mid] is unexamined
}
}
}
/** Stable merge of two sorted arrays: ties take from a first. */
static int[] mergeSorted(int[] a, int[] b) {
int[] out = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length) {
out[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
}
while (i < a.length) out[k++] = a[i++];
while (j < b.length) out[k++] = b[j++];
return out;
}
static void check(boolean ok, String what) {
if (!ok) throw new AssertionError("FAILED: " + what);
}
public static void main(String[] args) {
check(Arrays.equals(pairSumSorted(new int[]{1, 2, 4, 7, 11, 15}, 15), new int[]{2, 4}), "pair sum found");
check(pairSumSorted(new int[]{1, 2, 3}, 100) == null, "pair sum not found");
check(pairSumSorted(new int[]{}, 5) == null, "pair sum empty");
check(pairSumSorted(new int[]{Integer.MAX_VALUE - 1, Integer.MAX_VALUE}, 0) == null, "no overflow");
check(threeSum(new int[]{-1, 0, 1, 2, -1, -4}).equals(List.of(List.of(-1, -1, 2), List.of(-1, 0, 1))), "3sum");
check(threeSum(new int[]{0, 0, 0, 0}).equals(List.of(List.of(0, 0, 0))), "3sum zeros");
check(threeSum(new int[]{1, 2, 3}).isEmpty(), "3sum none");
int[] f = {2, 0, 2, 1, 1, 0};
dutchFlag(f);
check(Arrays.equals(f, new int[]{0, 0, 1, 1, 2, 2}), "dutch flag");
int[] empty = {};
dutchFlag(empty);
check(empty.length == 0, "dutch flag empty");
check(Arrays.equals(mergeSorted(new int[]{1, 3, 5}, new int[]{2, 4, 6, 8}), new int[]{1, 2, 3, 4, 5, 6, 8}), "merge");
check(Arrays.equals(mergeSorted(new int[]{}, new int[]{1}), new int[]{1}), "merge empty");
check(Arrays.equals(mergeSorted(new int[]{2, 2}, new int[]{2}), new int[]{2, 2, 2}), "merge ties");
System.out.println("all tests passed");
}
}
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <optional>
#include <utility>
#include <vector>
using std::vector;
// Indices (lo, hi) with a[lo] + a[hi] == target, or nullopt. a must be sorted.
std::optional<std::pair<int, int>> pairSumSorted(const vector<int>& a, int target) {
int lo = 0, hi = static_cast<int>(a.size()) - 1;
while (lo < hi) {
long long s = static_cast<long long>(a[lo]) + a[hi]; // avoid int overflow
if (s == target) return std::make_pair(lo, hi);
if (s < target) ++lo; // row lo is dead
else --hi; // column hi is dead
}
return std::nullopt;
}
// All distinct triplets summing to 0, each ascending, in lexicographic order.
vector<vector<int>> threeSum(vector<int> a) {
std::sort(a.begin(), a.end());
const int n = static_cast<int>(a.size());
vector<vector<int>> out;
for (int i = 0; i + 2 < n; ++i) {
if (i > 0 && a[i] == a[i - 1]) continue; // same first element
if (a[i] > 0) break; // all remaining positive
int lo = i + 1, hi = n - 1;
while (lo < hi) {
long long s = static_cast<long long>(a[i]) + a[lo] + a[hi];
if (s < 0) ++lo;
else if (s > 0) --hi;
else {
out.push_back({a[i], a[lo], a[hi]});
++lo; --hi;
while (lo < hi && a[lo] == a[lo - 1]) ++lo;
while (lo < hi && a[hi] == a[hi + 1]) --hi;
}
}
}
return out;
}
// In-place 3-way partition of values in {0,1,2}.
void dutchFlag(vector<int>& a) {
int lo = 0, mid = 0, hi = static_cast<int>(a.size()) - 1;
while (mid <= hi) {
if (a[mid] == 0) { std::swap(a[lo], a[mid]); ++lo; ++mid; }
else if (a[mid] == 1) { ++mid; }
else { std::swap(a[mid], a[hi]); --hi; } // mid stays: new a[mid] unexamined
}
}
// Stable merge of two sorted vectors: ties take from a first.
vector<int> mergeSorted(const vector<int>& a, const vector<int>& b) {
vector<int> out;
out.reserve(a.size() + b.size());
std::size_t i = 0, j = 0;
while (i < a.size() && j < b.size()) {
if (a[i] <= b[j]) out.push_back(a[i++]);
else out.push_back(b[j++]);
}
while (i < a.size()) out.push_back(a[i++]);
while (j < b.size()) out.push_back(b[j++]);
return out;
}
static void check(bool ok, const char* what) {
if (!ok) { std::cerr << "FAILED: " << what << "\n"; std::exit(1); }
}
int main() {
auto p = pairSumSorted({1, 2, 4, 7, 11, 15}, 15);
check(p && p->first == 2 && p->second == 4, "pair sum found");
check(!pairSumSorted({1, 2, 3}, 100), "pair sum not found");
check(!pairSumSorted({}, 5), "pair sum empty");
check(!pairSumSorted({2147483646, 2147483647}, 0), "no overflow");
vector<vector<int>> t = threeSum({-1, 0, 1, 2, -1, -4});
check(t == vector<vector<int>>{{-1, -1, 2}, {-1, 0, 1}}, "3sum");
check(threeSum({0, 0, 0, 0}) == vector<vector<int>>{{0, 0, 0}}, "3sum zeros");
check(threeSum({1, 2, 3}).empty(), "3sum none");
vector<int> f = {2, 0, 2, 1, 1, 0};
dutchFlag(f);
check(f == vector<int>{0, 0, 1, 1, 2, 2}, "dutch flag");
vector<int> e;
dutchFlag(e);
check(e.empty(), "dutch flag empty");
check(mergeSorted({1, 3, 5}, {2, 4, 6, 8}) == vector<int>{1, 2, 3, 4, 5, 6, 8}, "merge");
check(mergeSorted({}, {1}) == vector<int>{1}, "merge empty");
check(mergeSorted({2, 2}, {2}) == vector<int>{2, 2, 2}, "merge ties");
std::cout << "all tests passed\n";
return 0;
}
import assert from "node:assert/strict";
/** Indices [lo, hi] with nums[lo] + nums[hi] === target, or null. nums must be sorted. */
function pairSumSorted(nums: number[], target: number): [number, number] | null {
let lo = 0;
let hi = nums.length - 1;
while (lo < hi) {
const s = nums[lo] + nums[hi];
if (s === target) return [lo, hi];
if (s < target) lo++; // row lo is dead
else hi--; // column hi is dead
}
return null;
}
/** All distinct triplets summing to 0, each ascending, in lexicographic order. */
function threeSum(nums: number[]): number[][] {
const a = [...nums].sort((x, y) => x - y); // numeric sort, never the default lexicographic one
const out: number[][] = [];
for (let i = 0; i + 2 < a.length; i++) {
if (i > 0 && a[i] === a[i - 1]) continue; // same first element
if (a[i] > 0) break; // all remaining positive
let lo = i + 1;
let hi = a.length - 1;
while (lo < hi) {
const s = a[i] + a[lo] + a[hi];
if (s < 0) lo++;
else if (s > 0) hi--;
else {
out.push([a[i], a[lo], a[hi]]);
lo++;
hi--;
while (lo < hi && a[lo] === a[lo - 1]) lo++;
while (lo < hi && a[hi] === a[hi + 1]) hi--;
}
}
}
return out;
}
/** In-place 3-way partition of values in {0,1,2}. */
function dutchFlag(a: number[]): number[] {
let lo = 0;
let mid = 0;
let hi = a.length - 1;
while (mid <= hi) {
if (a[mid] === 0) {
[a[lo], a[mid]] = [a[mid], a[lo]];
lo++;
mid++;
} else if (a[mid] === 1) {
mid++;
} else {
[a[mid], a[hi]] = [a[hi], a[mid]];
hi--; // mid stays: new a[mid] unexamined
}
}
return a;
}
/** Stable merge of two sorted arrays: ties take from a first. */
function mergeSorted(a: number[], b: number[]): number[] {
const out: number[] = [];
let i = 0;
let j = 0;
while (i < a.length && j < b.length) {
if (a[i] <= b[j]) out.push(a[i++]);
else out.push(b[j++]);
}
while (i < a.length) out.push(a[i++]);
while (j < b.length) out.push(b[j++]);
return out;
}
assert.deepEqual(pairSumSorted([1, 2, 4, 7, 11, 15], 15), [2, 4]);
assert.equal(pairSumSorted([1, 2, 3], 100), null);
assert.equal(pairSumSorted([], 5), null);
assert.deepEqual(threeSum([-1, 0, 1, 2, -1, -4]), [[-1, -1, 2], [-1, 0, 1]]);
assert.deepEqual(threeSum([0, 0, 0, 0]), [[0, 0, 0]]);
assert.deepEqual(threeSum([1, 2, 3]), []);
assert.deepEqual(dutchFlag([2, 0, 2, 1, 1, 0]), [0, 0, 1, 1, 2, 2]);
assert.deepEqual(dutchFlag([]), []);
assert.deepEqual(dutchFlag([1]), [1]);
assert.deepEqual(mergeSorted([1, 3, 5], [2, 4, 6, 8]), [1, 2, 3, 4, 5, 6, 8]);
assert.deepEqual(mergeSorted([], [1]), [1]);
assert.deepEqual(mergeSorted([2, 2], [2]), [2, 2, 2]);
console.log("all tests passed");
Three implementation notes that are not cosmetic. First, Java and C++ widen to 64 bits before adding: int + int overflows silently for values near , and the test with Integer.MAX_VALUE - 1 and Integer.MAX_VALUE would wrap to a negative number and could even produce a false match for a negative target. Python integers are arbitrary precision and JavaScript numbers are doubles (exact up to ), so those two languages are safe for typical constraints. Second, TypeScript's Array.prototype.sort without a comparator sorts lexicographically — [10, 9, 1].sort() gives [1, 10, 9] — so always pass (x, y) => x - y. Third, the 3-sum early break when a[i] > 0 is an optimisation, not a correctness requirement; it is valid because once the smallest of the three is positive, no triplet can sum to zero.
Variant: the generic "compact in place" template
Family B problems share one skeleton. This is a fragment to adapt, not to run:
# fragment — template only
def compact_in_place(a, keep):
w = 0
for r in range(len(a)):
if keep(a[r], w, a): # the predicate may look at what has been kept so far
a[w] = a[r]
w += 1
return w # a[:w] is the result; a[w:] is garbage
remove duplicates is keep = lambda x, w, a: w == 0 or a[w-1] != x; move zeroes is keep = lambda x, w, a: x != 0 followed by zero-filling a[w:]; remove element is keep = lambda x, w, a: x != val. This is literally what C++'s std::remove_if does, which is why it returns the new logical end and leaves the tail unspecified — the erase–remove idiom v.erase(std::remove_if(...), v.end()) then physically shrinks the container.
Real-world uses
Sort-merge join in databases. When both inputs of a join are sorted on the join key (because of an index, a previous sort, or a GROUP BY that needed it anyway), the executor walks both inputs with one cursor each and emits matching rows — Family C with a twist for duplicate keys on both sides (it must iterate the cross product of equal-key runs, which is why planners track whether a key is unique). PostgreSQL's planner chooses between hash join, nested loop and merge join by cost; merge join wins when the sort is free and the inputs are large, because its access pattern is sequential. See Query Planning & Optimization.
External merge sort and merging sorted runs. Sorting data larger than memory means sorting chunks that fit, writing each as a sorted run, then merging the runs. Two runs merge with the Family C loop; runs use a heap over the heads, which is the same idea with the "pick the smaller head" step replaced by a heap pop (Heaps). Python's heapq.merge and the merge phase of every external sort do this. The course page "Sorting in the Real World" (Module 2) covers run sizes, replacement selection and how Timsort finds and merges natural runs.
LSM-tree compaction in storage engines. RocksDB, LevelDB and Cassandra store data as sorted immutable files (SSTables). Compaction merges several overlapping SSTables into one, walking each with a cursor and emitting the newest version of each key — a k-way merge where the tie-break rule is "larger sequence number wins" and tombstones delete. It is in-place compaction in the sense that the output replaces the inputs; the memory footprint is one block per input file regardless of total size. See Storage Engines and the related Write-Ahead Logging.
Diff and merge of sorted logs. Correlating two time-ordered event streams — two servers' logs, two replicas' operation logs, a trace from a client and a trace from a server — is a Family C walk ordered by timestamp. Unix comm (lines common to two sorted files), join (relational join on sorted text) and sort -m (merge already-sorted files without re-sorting) are two-pointer programs that have shipped since the 1970s.
Standard libraries. std::partition (Hoare-style, opposite ends), std::stable_partition, std::unique (Family B; it is the "remove adjacent duplicates" loop and expects sorted input for full deduplication), std::remove/std::remove_if, std::merge, std::inplace_merge, std::set_intersection/std::set_union/std::set_difference (Family C over sorted ranges). Knowing the pattern lets you predict their complexities and preconditions without reading the documentation.
Quicksort partition. Lomuto partition (one read pointer, one write pointer, pivot at the end) is Family B; Hoare partition (two pointers converging from the ends, swapping out-of-place elements) is Family A. Three-way partitioning (Bentley–McIlroy, or the Dutch flag) is what makes quicksort fast on inputs with many duplicates, and is what Java's dual-pivot quicksort and most std::sort implementations do in some form.
Pitfalls & edge cases
A loop where neither pointer moves. Every branch of a two-pointer loop must advance at least one pointer, or the loop never terminates. The classic bug is handling the equality case in 3-sum by recording the triplet and then only running the "skip duplicates" loops — which do nothing if the neighbours are different — without the unconditional lo += 1; hi -= 1. Write the unconditional moves first, then the skips.
Duplicates in 3-sum / 4-sum. Forgetting the first-element skip (a[i] == a[i-1]) produces duplicate triplets; skipping every equal element including the first (while a[i] == a[i+1]: i += 1 before processing i) misses triplets like [-1, -1, 2] that legitimately use two equal values. The rule is: process the first occurrence, skip the subsequent ones.
Unsorted input. Family A's correctness proof uses sortedness in the maintenance step. Run pair sum on an unsorted array and it will happily miss answers. If a problem says "array" without "sorted" and order does not matter for the output, sort first (and remember that sorting costs and loses original indices unless you sort index pairs).
Integer overflow in sums. Java int and C++ int are 32-bit. nums[lo] + nums[hi] with values up to overflows at . Three-way sums overflow even sooner. Widen to long/long long. In TypeScript, integers are exact only below , which is fine for typical constraints but not for 64-bit problem inputs — use BigInt there.
lo < hi versus lo <= hi. For pair problems the pointers must be distinct, so lo < hi. For Dutch flag the loop is mid <= hi because a[mid] with mid == hi is still unexamined; writing mid < hi leaves the last element unsorted (try [1, 0]: with <, the loop ends immediately and 0 stays at the end). For palindrome checks, lo < hi suffices because the middle character of an odd-length string needs no comparison.
Off-by-one in the write pointer. For "remove duplicates", w starts at 1 and the comparison is against nums[w-1], the last kept element, not nums[r-1], the last read element. Comparing against nums[r-1] happens to work for sorted input (equal elements are adjacent) but breaks for the "remove all occurrences of val" variant, where the kept element and the previous read element differ.
Empty and single-element inputs. hi = len - 1 is -1 for an empty array; while lo < hi then runs zero times, which is correct, but any code that reads nums[hi] before the loop crashes. Dutch flag on an empty array: mid = 0, hi = -1, loop body never runs. Merge with one empty input must still copy the other.
Container with most water on equal heights. Moving the wrong pointer when h[lo] == h[hi] does not break correctness (either is safe, as shown), but some people "fix" the tie by moving neither, which is an infinite loop. Pick one.
Strings with Unicode. In JavaScript and Java, s[i]/s.charAt(i) index UTF-16 code units; a character outside the Basic Multilingual Plane (an emoji, many CJK extension characters) is two units, and reversing or palindrome-checking by code unit splits it. Iterate over code points (Array.from(s), s.codePoints()) when the input is not guaranteed ASCII. See Strings in Depth.
Variations
k pointers. Dutch flag uses three; the generalisation to categories in one pass needs boundaries and is rarely worth it over counting sort (two passes, trivially correct). k-sum uses nested cursors, the innermost two converging.
Pointer + hash map. When one sequence is sorted and the other is not, or when you need the complement of a running value, combine a pointer with a hash map: "two sum" on unsorted input is a single pointer plus a map from value to index. "Longest substring without repeating characters" is two pointers (a window) plus a map from character to last index — see Sliding Window.
Two pointers on two strings. "Is subsequence", "backspace compare", "compare version numbers" (walk both strings chunk by chunk between dots), "longest common prefix of two strings", "one edit distance" (walk both; on the first mismatch, skip one character in the longer or both in equal-length strings and require the rest to match).
Circular arrays. Opposite-end techniques on a ring need care because there are no ends. The standard trick is to double the array conceptually (index modulo , let hi run up to ) so that every window of length appears contiguously once. The sliding-window page covers the doubling trick in detail.
Meet-in-the-middle on sorted lists. 4-sum over four different arrays (count tuples ) becomes: enumerate all sums and all sums, sort both lists, and run Family A on them — instead of . The two-pointer step is the same; the inputs are synthetic.
Sliding window. The special case where both pointers move right and the content between them is what you measure. Different invariant ("the window is the longest/shortest valid one ending at r"), different page: Sliding Window.
Fast/slow and -apart pointers on linked lists — Linked Lists. Monotonic deque windows — Monotonic Stack & Deque. Interval sweeps that walk two sorted interval lists (interval intersection) — Intervals.
Practice ladder
Easy → hard. Descriptions are paraphrased; follow the links for the exact statements.
1. Reverse String (LeetCode 344) — reverse a character array in place. Teaches the Family A skeleton with the trivial rule "always move both".
Hint
Swap s[lo] and s[hi], then lo += 1, hi -= 1, while lo < hi.
2. Valid Palindrome (LeetCode 125) — is a string a palindrome after dropping non-alphanumerics and ignoring case? Teaches pointer skipping inside the loop and why it is still .
Hint
Inside the main loop, run while lo < hi and not s[lo].isalnum(): lo += 1 and the mirror for hi before comparing. Each pointer only ever moves one way, so total work is linear.
3. Two Sum II — Input Array Is Sorted (LeetCode 167) — the canonical pair sum, 1-indexed output. Teaches Family A exactly as proved above.
Hint
The page's pair_sum_sorted, then add 1 to both indices.
4. Move Zeroes (LeetCode 283) — push all zeroes to the end keeping the order of the rest. Teaches Family B with a stability requirement.
Hint
Write pointer w for the next non-zero slot. For each r, if nums[r] != 0, swap nums[w] and nums[r] and w += 1.
5. Remove Duplicates from Sorted Array (LeetCode 26) — compact a sorted array to its distinct values, return the new length. Teaches the "compare against last kept" detail.
Hint
w = 1; for r in 1..n-1: if nums[r] != nums[w-1], write and advance w.
6. Squares of a Sorted Array (LeetCode 977) — square each element of a sorted array (which may contain negatives) and return the result sorted, in . Teaches that the largest squares are at the ends, so fill the output from the back.
Hint
The largest absolute value is at lo or hi. Compare |nums[lo]| with |nums[hi]|, write the larger square to out[k] for k from n-1 down to 0, move that pointer.
Solution
def sorted_squares(nums: list[int]) -> list[int]:
n = len(nums)
out = [0] * n
lo, hi = 0, n - 1
for k in range(n - 1, -1, -1): # fill from the largest square down
if abs(nums[lo]) > abs(nums[hi]):
out[k] = nums[lo] * nums[lo]
lo += 1
else:
out[k] = nums[hi] * nums[hi]
hi -= 1
return out
assert sorted_squares([-4, -1, 0, 3, 10]) == [0, 1, 9, 16, 100]
assert sorted_squares([-7, -3, 2, 3, 11]) == [4, 9, 9, 49, 121]
assert sorted_squares([5]) == [25]
assert sorted_squares([-2, -1]) == [1, 4]
print("ok")
time, for the output (which is required), extra. Invariant: out[k+1..n-1] holds the largest squares in order, and they all came from outside [lo, hi].
7. Merge Sorted Array (LeetCode 88) — merge nums2 into nums1, which has enough trailing space, in place. Teaches Family C run backwards so that nothing is overwritten before it is read.
Hint
Three pointers: i = m-1, j = n-1, k = m+n-1. Write the larger of nums1[i], nums2[j] to nums1[k]. When nums2 is exhausted you can stop; when nums1 is exhausted copy the rest of nums2.
8. Is Subsequence (LeetCode 392) — is s a subsequence of t? Teaches the greedy earliest-match argument. The follow-up (many s queries against one t) is a different algorithm: precompute, for each position and character, the next occurrence.
Hint
One pointer into s; advance it whenever t[j] == s[i]. Answer is i == len(s).
9. Backspace String Compare (LeetCode 844) — two strings typed with # meaning backspace; are the results equal, in space? Teaches two pointers walking backwards with a pending-skip counter.
Hint
From the end of each string, find the next character that survives: count #s, skip that many letters. Compare survivors pairwise. Mismatch or one side ending early → false.
Solution
def backspace_compare(s: str, t: str) -> bool:
def next_live(x: str, i: int) -> int:
"""Index of the next surviving char at or before i, or -1."""
skip = 0
while i >= 0:
if x[i] == '#':
skip += 1
elif skip > 0:
skip -= 1
else:
return i
i -= 1
return -1
i, j = len(s) - 1, len(t) - 1
while True:
i = next_live(s, i)
j = next_live(t, j)
if i < 0 or j < 0:
return i < 0 and j < 0 # both exhausted together
if s[i] != t[j]:
return False
i -= 1
j -= 1
assert backspace_compare("ab#c", "ad#c") is True
assert backspace_compare("ab##", "c#d#") is True
assert backspace_compare("a#c", "b") is False
assert backspace_compare("a##c", "#a#c") is True
assert backspace_compare("", "") is True
print("ok")
time, space. Each pointer moves monotonically left, so the inner skipping loops total at most the string length.
10. Container With Most Water (LeetCode 11) — maximise width × min height over all pairs. Teaches the exchange argument for "move the shorter side".
Hint
Record (hi - lo) * min(h[lo], h[hi]); move the pointer at the shorter line. Prove to yourself that the retired pointer cannot be in a better pair.
11. Sort Colors (LeetCode 75) — one-pass in-place sort of values {0, 1, 2}. Teaches the Dutch national flag invariant.
Hint
Three pointers lo, mid, hi; loop while mid <= hi; on a 2, swap with hi and do not advance mid.
12. 3Sum (LeetCode 15) — all distinct triplets summing to zero. Teaches sort-fix-two-pointers and duplicate skipping.
Hint
The page's three_sum. Process the first occurrence of each a[i], skip the rest; after a hit, move both pointers then skip equal neighbours.
13. Sum of Two Values (CSES 1640) — find two positions with a given sum, , print 1-based original positions or IMPOSSIBLE. Teaches that two pointers on sorted input needs an index map to recover original positions — or that a hash map is simpler here.
Hint
Sort pairs (value, original_index), run pair sum, print the stored indices. Or a dictionary from value to index in one pass. Both are or better and both pass.
14. Trapping Rain Water (LeetCode 42) — total water trapped between bars. Teaches the two-maxima invariant and why one side can be settled without seeing the other.
Hint
lmax, rmax; settle the side whose current bar is lower. Re-read the proof in Mechanics before coding.
Solution
def trap(h: list[int]) -> int:
lo, hi = 0, len(h) - 1
lmax = rmax = 0
water = 0
while lo < hi:
if h[lo] < h[hi]:
lmax = max(lmax, h[lo])
water += lmax - h[lo] # maxRight(lo) >= lmax, proved on the page
lo += 1
else:
rmax = max(rmax, h[hi])
water += rmax - h[hi]
hi -= 1
return water
def trap_brute(h: list[int]) -> int:
n = len(h)
return sum(min(max(h[:i + 1]), max(h[i:])) - h[i] for i in range(n))
assert trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert trap([4, 2, 0, 3, 2, 5]) == 9
assert trap([]) == 0
assert trap([3, 0, 1, 2]) == 3
import random
random.seed(7)
for _ in range(300):
arr = [random.randint(0, 9) for _ in range(random.randint(1, 12))]
assert trap(arr) == trap_brute(arr), arr
print("ok")
time, space. The randomized comparison against the brute force is the habit recommended in Testing & Debugging Algorithms.
15. 4Sum (LeetCode 18) — all distinct quadruplets summing to a target. Teaches nesting one more level with duplicate skipping at every level, and the overflow trap (targets up to , four values up to each).
Hint
Two outer loops fixing i < j, each skipping repeated values; inner two pointers as in 3-sum. Widen sums to 64 bits in Java/C++.
Solution
def four_sum(nums: list[int], target: int) -> list[list[int]]:
a = sorted(nums)
n = len(a)
out: list[list[int]] = []
for i in range(n - 3):
if i > 0 and a[i] == a[i - 1]:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and a[j] == a[j - 1]:
continue
lo, hi = j + 1, n - 1
while lo < hi:
s = a[i] + a[j] + a[lo] + a[hi]
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
out.append([a[i], a[j], a[lo], a[hi]])
lo += 1
hi -= 1
while lo < hi and a[lo] == a[lo - 1]:
lo += 1
while lo < hi and a[hi] == a[hi + 1]:
hi -= 1
return out
assert four_sum([1, 0, -1, 0, -2, 2], 0) == [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
assert four_sum([2, 2, 2, 2, 2], 8) == [[2, 2, 2, 2]]
assert four_sum([1, 2, 3], 6) == []
print("ok")
time after an sort, extra space beyond the output.
Common mistakes & interview follow-ups
"Why not just use a hash map?" For a single pair on unsorted input, a hash map is the better answer: with original indices. Two pointers wins when the input is already sorted (then it is space), when you need all pairs/triplets with deduplication, or when memory is constrained. Say this trade-off out loud; it is what the question is testing.
"What if the array is a stream?" Family A needs random access to both ends, so it does not apply. Family C does if both streams arrive sorted (that is exactly a merge of two sorted streams). For "pair sum" on a stream you need a hash set of seen values ( memory) — or, if memory is bounded, a probabilistic structure with false positives (Probabilistic Data Structures).
"What if memory is limited to and the input is unsorted?" Then you must sort in place first (, heapsort or introsort), then two pointers. Point out that sorting loses the original indices; if those are required you cannot do better than extra space.
"Count the pairs instead of finding one." With distinct values, each match counts once and both pointers move. With duplicates, when nums[lo] + nums[hi] == target count the run lengths: if nums[lo] != nums[hi], multiply the lengths of the two equal runs and skip both; if nums[lo] == nums[hi], all remaining elements are equal and there are pairs.
"Pairs with sum less than / at most the target." When nums[lo] + nums[hi] <= target, every j in (lo, hi] also works with lo, so add hi - lo to the count and move lo. Otherwise move hi. Still .
"Closest pair to the target." Track best = min(|sum - target|) and move the pointers exactly as in pair sum. Correct because the same elimination argument shows the retired pointer cannot be in a pair with a smaller difference. 3Sum Closest (LeetCode 16) is this with an outer loop.
"Container with most water — what if you can remove one bar?" Not a two-pointer question any more; the interviewer is checking whether you notice. Brute force over the removed bar is ; discuss whether that is acceptable before optimising.
"Dutch flag with four colours?" Possible with four boundaries but error-prone; counting sort in two passes is simpler and the interviewer usually accepts "two-pass counting sort, , counts" with the observation that one-pass is only interesting when the array does not fit in memory twice.
"Is your merge stable? Why does it matter?" Yes if ties take from the first input. Stability lets merge sort sort by multiple keys in successive passes and lets a sort-merge join preserve the order of one input.
Quick quiz
1. In pair sum on a sorted array, the loop condition is lo < hi. What goes wrong if you write lo <= hi?
Answer
When lo == hi the "pair" uses the same element twice: nums[lo] + nums[lo]. For nums = [1, 2, 5] and target = 10 you would return (2, 2), which is not a valid pair of distinct indices.
2. State the Dutch national flag invariant and say which pointer does not move when a[mid] == 2, and why.
Answer
a[0..lo-1] all 0, a[lo..mid-1] all 1, a[mid..hi] unknown, a[hi+1..] all 2. When a[mid] == 2 we swap a[mid] with a[hi] and decrement hi; mid stays because the element that just arrived from position hi has not been examined yet.
3. In "container with most water", heights are [5, 5]-style ties at both ends. Is moving lo, moving hi, or moving both correct?
Answer
All three are correct. The pair (lo, hi) has been recorded; any pair keeping exactly one of the two endpoints has smaller width and a height at most h[lo] = h[hi], so it cannot beat the recorded area. Moving neither is the only wrong choice (infinite loop).
4. Why does "backspace string compare" walk the strings from the end rather than the start?
Answer
A # deletes the character before it, so whether a character survives depends on characters to its right. Walking from the end, by the time you reach a character you have already counted all backspaces that could delete it.
5. You run pair sum on [3, 1, 4, 1, 5] with target 6 and it returns "not found". Is that a bug in the algorithm?
Answer
No — a precondition violation. The array is not sorted; the elimination step ("row lo is dead because nums[j] <= nums[hi]") is false for unsorted input. Sort first (giving [1, 1, 3, 4, 5], where the pair 1 + 5 is found), or use a hash set.
Further reading / sources
- Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — §2.3.1 (merge), §7.1 (Lomuto partition), Problem 7-1 (Hoare partition).
- Edsger W. Dijkstra, A Discipline of Programming (1976), chapter 14, "The problem of the Dutch national flag" — the original statement and invariant-based derivation.
- Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed. — §2.3 (quicksort, three-way partitioning).
- Jon Bentley and M. Douglas McIlroy, "Engineering a Sort Function", Software: Practice and Experience 23(11), 1993 — three-way partitioning in production
qsort. - Allan Grønlund and Seth Pettie, "Threesomes, Degenerates, and Love Triangles", FOCS 2014 (arXiv:1404.0799) — the state of the 3SUM problem.
- cp-algorithms, Two pointers technique — concise competitive-programming treatment.
- C++ reference for
std::partition,std::unique,std::merge— preconditions and complexities.
Lessons: previous — Arrays & Strings (overview) · next — Sliding Window · module — Linear Data Structures.
Related Archon pages: Prefix Sums · Linked Lists · Hash Tables · Intervals · Sorting & Searching · How to Solve Any Problem · Complexity Analysis.