Two Pointers

1. The signal

Reach for two pointers when you see:

• A sorted array and a question about a pair or triple.
• “Find two numbers that sum to X.”
• A palindrome check, or comparing a sequence against its reverse.
• Something monotone: as one end moves in, a quantity only ever increases or decreases.
• “In place”, “O(1) extra space”, on an array.

If the array isn’t sorted but order doesn’t matter, sorting first (O(n log n)) to unlock the pattern is usually the right trade. If the answer must be indices, sorting destroys them — that’s why plain Two Sum is a hash map problem and Two Sum II is a two-pointer one.

2. The template

int l = 0, r = n - 1;
while (l < r) {
    if (condition(a[l], a[r])) {
        // record or return
    }
    if (needBigger) l++;      // say WHY discarding a[l] is safe
    else r--;                 // say WHY discarding a[r] is safe
}

let l = 0, r = n - 1;
while (l < r) {
  if (condition(a[l], a[r])) { /* record or return */ }
  if (needBigger) l++;
  else r--;
}

That’s it. The code is trivial. The comment is the hard part, and it’s the only part interviewers care about.

3. Why it’s correct

Two pointers works because of an exchange argument: when you move a pointer, you must be able to prove that every pair you just discarded was either already considered or could never be the answer.

• Sorted pair sum: if a[l] + a[r] < target, then a[l] paired with anything still in range is also too small, because a[r] is the largest value left. So a[l] can be discarded entirely.
• Container With Most Water: the shorter wall caps the height, and the width only shrinks from here. Keeping the shorter wall can never produce a bigger area than the one you just measured.
• Trapping Rain Water: the pointer on the shorter side already knows its own max for certain, because the taller side guarantees a wall at least that high somewhere beyond it.

If you cannot state that argument for a problem, two pointers is the wrong pattern — you’ll write code that passes the examples and fails a hidden case.

4. Complexity

O(n) time, since each pointer only ever moves inward and they meet once. O(1) extra space. Add O(n log n) if you had to sort first — and note the sort then dominates.

5. Variants

6. Traps

1. while (l < r) vs while (l <= r). For pair problems it’s < — an element must not pair with itself. For search-style scans it’s often <=. Decide from the invariant, not by trying both.
2. Forgetting to skip duplicates. In 3Sum this is the difference between correct and almost correct, and it’s the most common reason a submission fails.
3. Applying it to unsorted data. Without order there’s no safe discard, and the pattern silently produces wrong answers rather than obviously breaking.
4. Moving both pointers when only one should move. After finding a match in 3Sum you move both; when the sum is merely too small you move only l. Confusing the two loses answers.

7. Problems, easiest first

1. Valid Palindrome — the pattern with no arithmetic
2. Two Sum II — the canonical version
3. Container With Most Water — the exchange argument
4. 3Sum — fix one, two-pointer the rest, skip duplicates
5. Trapping Rain Water — the hard one; expect to need the walkthrough