05 — Two Pointers

The core idea

Two pointers replaces a nested loop by exploiting order. The precondition is always the same:

A single comparison must let you rule out a whole range of candidates.

Sorted input is the usual source of that guarantee.

Why it's O(n) even though it looks like it might revisit

The pointers only ever move forward (or toward each other). Neither ever goes back. So between them they take at most n steps total, no matter how the loop is structured. That's the same aggregate argument from 01.

Variant A — converging pointers (opposite ends)

One pointer at the start, one at the end, walking toward each other.

int lo = 0, hi = n - 1;
while (lo < hi) {
    if (found) { /* record answer */ lo++; hi--; }
    else if (tooSmall) lo++;      // only increasing lo can help
    else hi--;                    // only decreasing hi can help
}

Worked example: Two Sum II (sorted input)

numbers = [2, 7, 11, 15], target = 9.

int lo = 0, hi = numbers.length - 1;
while (lo < hi) {
    int sum = numbers[lo] + numbers[hi];
    if (sum == target) return new int[]{lo + 1, hi + 1};   // 1-indexed in this problem
    if (sum < target) lo++;       // need a BIGGER sum -> move lo right, to a bigger value
    else hi--;                    // need a SMALLER sum -> move hi left, to a smaller value
}

Trace:

Why this is correct — the elimination argument

This is what interviewers want to hear, so learn to say it:

"The array is sorted. When sum < target, numbers[lo] is too small to pair with numbers[hi] — and numbers[hi] is the largest remaining value. So numbers[lo] can't pair with anything still in range. I can discard lo entirely and move right. Each step eliminates a whole row of the pair matrix, so I get O(n) instead of O(n²)."

Picture the n × n grid of all pairs. The brute force checks every cell. Two pointers walks a single path from one corner, and each step deletes an entire row or column.

Why lo < hi and not lo <= hi

lo < hi means the two pointers must select distinct elements. If they met (lo == hi) you'd be pairing an element with itself.

Use lo <= hi only when a single middle element is a valid answer on its own — which happens in binary search (10), not usually here.

Valid Palindrome — same skeleton, plus skipping

"A man, a plan, a canal: Panama" is a palindrome once you ignore punctuation and case.

int l = 0, r = s.length() - 1;
while (l < r) {
    while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;   // skip junk from the left
    while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;   // skip junk from the right
    if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false;
    l++; r--;
}
return true;

The l < r check inside the inner loops is mandatory. Without it, a string of pure punctuation like ".,;" would run l straight past the end of the string and throw. The guard stops both pointers the moment they meet.

Variant B — same-direction (slow / fast)

Both pointers move the same way. slow marks where to write, fast scans ahead. This is the in-place filter pattern.

int slow = 0;
for (int fast = 0; fast < n; fast++) {
    if (keep(nums[fast])) {
        nums[slow++] = nums[fast];     // write it at slow, then advance slow
    }
}
return slow;                           // slow is now the new length

Trace — removing zeros from [0, 1, 0, 3, 2]:

First 3 elements are [1, 3, 2] — the kept values. Everything past slow is leftover garbage, which is why you return the length.

Why overwriting is safe: slow never exceeds fast, so you only ever write to positions you've already read past.

In linked lists this same slow/fast shape becomes cycle and midpoint detection — see 11.

Variant C — sort, then fix-and-scan (k-sum)

For k-sum, sort first, then fix k - 2 indices with loops and solve the remaining 2-sum with converging pointers.

3Sum — find all unique triples summing to zero

Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();

for (int i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) break;                             // sorted: no triple can reach 0 now
    if (i > 0 && nums[i] == nums[i - 1]) continue;      // skip duplicate anchors

    int l = i + 1, r = nums.length - 1;
    while (l < r) {
        int sum = nums[i] + nums[l] + nums[r];
        if (sum < 0) l++;
        else if (sum > 0) r--;
        else {
            res.add(Arrays.asList(nums[i], nums[l], nums[r]));
            l++; r--;
            while (l < r && nums[l] == nums[l - 1]) l++;  // skip duplicate seconds
        }
    }
}
return res;

Trace with nums = [-1, 0, 1, 2, -1, -4]:

Sorted: [-4, -1, -1, 0, 1, 2]

Result: [[-1,-1,2], [-1,0,1]]. ✓

Three details that separate correct from nearly-correct

1. Dedup the anchor: if (i > 0 && nums[i] == nums[i-1]) continue;

Without it, i = 2 (the second −1) would regenerate [-1,-1,2] and [-1,0,1]. The i > 0 guard is mandatory — at i = 0 there is no nums[-1] to read.

2. Dedup after recording, not before.

res.add(...);
l++; r--;
while (l < r && nums[l] == nums[l - 1]) l++;   // now skip repeats

You must record the triple first, then skip past duplicates of the element you just used. Skipping first would lose valid triples.

3. Sorting is what makes dedup cheap.

Sorted input puts equal values next to each other, so "is this a duplicate?" is a single comparison with the neighbour. Unsorted, you'd need a Set of canonical triples — extra space and hashing cost.

On the cost of sorting: it's O(n log n), but the scan is O(n²), which dominates. The sort is free. Say that — candidates often apologize for sorting as though it were a cost.

Generalizes: k-sum is O(n^(k-1)).

Variant D — greedy width/height trade

Container With Most Water: height = [1,8,6,2,5,4,8,3,7]. Pick two lines; water held is width × min(the two heights). Maximize it.

int l = 0, r = height.length - 1, best = 0;
while (l < r) {
    int area = (r - l) * Math.min(height[l], height[r]);
    best = Math.max(best, area);
    if (height[l] < height[r]) l++;      // move the SHORTER wall
    else r--;
}
return best;

Trace (first few steps):

Best = 49. ✓

Why moving the shorter wall is the right move

This argument is the question — have it as one sentence:

"Area is width × min(left, right). Moving either pointer inward always reduces width. If I move the taller wall, the shorter one still caps the height — so height can't improve and width got smaller. Every pair I'd form that way is already worse than what I have. Moving the shorter wall is the only move that can possibly raise the height enough to beat the lost width. So it's safe to discard the shorter wall."

That's an exchange argument — the same proof style as greedy algorithms (20).

Variant E — two pointers with running maxima

Trapping Rain Water: height = [0,1,0,2,1,0,1,3,2,1,2,1]. How much water is trapped?

The governing formula

For each position i:

water at i = min(tallest wall to the left, tallest wall to the right) - height[i]

Water is held up by the shorter of the two surrounding walls (it spills over the lower one), minus whatever ground is already there.

Three implementations. Interviewers escalate through them, so know all three.

1. Prefix arrays — O(n) time, O(n) space. Clearest to explain.

int n = height.length;
int[] maxLeft = new int[n], maxRight = new int[n];

maxLeft[0] = height[0];
for (int i = 1; i < n; i++) maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);

maxRight[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) maxRight[i] = Math.max(maxRight[i + 1], height[i]);

int water = 0;
for (int i = 0; i < n; i++) water += Math.min(maxLeft[i], maxRight[i]) - height[i];
return water;

Partial trace on [0,1,0,2,1,0,1,3,2,1,2,1]:

Water so far: 5. (Total for the full array is 6.)

Write this version first — it makes the formula visible.

2. Two pointers — O(n) time, O(1) space. The optimal.

int l = 0, r = height.length - 1;
int leftMax = 0, rightMax = 0, water = 0;

while (l < r) {
    if (height[l] < height[r]) {
        leftMax = Math.max(leftMax, height[l]);
        water += leftMax - height[l];
        l++;
    } else {
        rightMax = Math.max(rightMax, height[r]);
        water += rightMax - height[r];
        r--;
    }
}
return water;

Why you can drop the arrays — the invariant:

"Suppose height[l] < height[r]. Then there's a wall of height at least height[r] somewhere to the right of l, so the true maxRight at position l is at least height[r], which is greater than height[l]. Since min(maxLeft, maxRight) is what matters, and maxRight is guaranteed to be the larger of the two, the answer at l is determined by leftMax alone. I never need to know the actual maxRight."

The other branch is symmetric. Being able to state that invariant is exactly what the question tests — the code is four lines.

3. Monotonic stack — fills water in horizontal layers. See 09.

Two pointers vs. sliding window

These are confused constantly. The distinction:

The tell: if you care about what's between the pointers, it's a window (08). If you only care about the two elements you're pointing at, it's two pointers.

Recognition checklist

Complexity summary