Two PointersAlgorithmaka converging pointers, left-right pointers, squeeze

Two Pointers (Opposite Ends)

Walk one pointer in from each end of a sorted (or monotone-bounded) array, moving whichever side cannot improve the answer.

▶ VisualizePattern: Two PointersPractice (4)
Progress

Overview

Two pointers from opposite ends replaces a nested O(n²) pair scan with a single O(n) pass. Start l = 0, r = n - 1, look at the pair (a[l], a[r]), and use a monotonic property of the input to decide which pointer to move inward. Each step discards one index for good, so the loop runs at most n - 1 times.

The technique needs an ordering that makes one move provably safe. For pair sums that ordering is sortedness; for container-with-most-water-style problems it is that the width only shrinks, so the shorter wall is the one worth abandoning.

sortedO(n)in-placepair sumsqueeze

Intuition

A mental model before the formal terms.

Picture a sorted row of numbered cards. Pick up the leftmost (smallest) and rightmost (largest). If their sum is too small, the *only* way to raise it is to swap out the smallest card — the largest is already the biggest thing available. If the sum is too big, swap out the largest. You never need to look back at a card you dropped.

For the water container, think of two walls and the water between them. Moving either wall inward makes the pool narrower. If you move the taller wall the height is still capped by the shorter one, so the area can only fall. Moving the shorter wall is the only move that might help.

How it works

  1. Sort the input if the problem does not guarantee order (O(n log n), and only if indices need not be preserved — otherwise sort pairs of (value, index)).
  2. Initialize l = 0, r = n - 1.
  3. While l < r: evaluate the candidate formed by a[l] and a[r].
  4. If the candidate is exactly what you want, record it. Then move a pointer (or both) to look for further answers.
  5. If the candidate is "too small", l++; if "too big", r--. The direction is determined by which endpoint is the binding constraint.
  6. Stop when the pointers meet. Every pair was either examined or ruled out by an earlier move.

Why it works

Invariant: the answer, if it exists, uses indices in [l, r]. Initially that is the whole array. When a[l] + a[r] < target, every pair (l, j) with j ≤ r also sums to less than target because a[j] ≤ a[r]. So index l cannot participate in any answer with anything still in range and can be dropped. The symmetric argument justifies r-- when the sum is too large. The invariant is preserved, and when l == r no pair remains.

For maximum-area-style problems the argument is about elimination of a *whole set* of pairs: if h[l] < h[r], every container (l, j) for l < j < r has height ≤ h[l] and width < r - l, so all of them are worse than (l, r) which was already measured. Dropping l loses nothing.

Each iteration moves at least one pointer by one, and pointers never move outward, so there are at most n - 1 iterations: O(n) after any sort.

Recognition

How to tell a problem wants this.

  • The input is sorted, or the problem lets you sort it (order of output does not matter, or you may return values instead of indices).
  • You are asked for a pair (or triple, via an outer loop) meeting a sum/difference/product condition: "two numbers that add up to", "closest to target", "count pairs with sum less than k".
  • Phrases like "in-place", "O(1) extra space", "without using a hash map", or "the array is sorted in non-decreasing order" — the sortedness hint is the interviewer telling you not to reach for Hash Map.
  • Symmetric problems: "is it a palindrome", "reverse in place", "container / trapping water" — one pointer from each end walking toward the middle.
  • Constraints of n ≤ 10^5 with an obvious O(n²) brute force point at either two pointers or hashing; if the array is sorted, two pointers is the O(1)-space option.
“sorted array” → Two Pointers

Interactive visualization

Play, step, change the input. ← → and space work too.

1
0
↑lo
3
1
4
2
6
3
8
4
11
5
15
6
18
7
21
8
↑hi
1/5Sorted array of 9 values, target 19. Put lo at the smallest and hi at the largest element; the sortedness lets each comparison discard one endpoint.
lo pointerhi pointerEliminatedPair found
PseudocodeLearn Two Pointers (Opposite Ends) →
1lo = 0, hi = n - 1
2while lo < hi:
3  s = a[lo] + a[hi]
4  if s == target: return (lo, hi)
5  if s < target: lo += 1
6  else: hi -= 1
7return not found
Variables
lo0
hi8
target19
Complexity
best O(1)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1l = 0, r = n - 1
2while l < r:
3  s = a[l] + a[r]
4  if s == target: return (l, r)
5  if s < target: l = l + 1   # a[l] is too small for any partner ≤ a[r]
6  else: r = r - 1            # a[r] is too big for any partner ≥ a[l]
7return none

Implementations

1# Two Sum II: 1-based indices of two numbers in a sorted array summing to target
2def two_sum_sorted(a: list[int], target: int) -> list[int]:
31 · Initialize pointers at both ends
4    l, r = 0, len(a) - 1
52 · Squeeze while the pointers have not met
6    while l < r:
73 · Evaluate the current pair (64-bit to avoid overflow)
8        s = a[l] + a[r]  # Python ints never overflow
9        if s == target:
10            return [l + 1, r + 1]
114 · Move the pointer that cannot improve the answer
12        if s < target:
13            l += 1
14        else:
15            r -= 1
165 · No pair found
17    return [-1, -1]
Walkthrough
  1. Tuple assignment l, r = 0, len(a) - 1 initialises both pointers in one statement.
  2. Python integers are arbitrary precision, so a[l] + a[r] can never overflow — the comment marks where other languages need care.
  3. Returning a list[int] matches the LeetCode signature; a tuple would be the more Pythonic choice for a fixed pair.
  4. Explicit += 1 / -= 1 because Python has no ++ operator.
  5. The final return [-1, -1] keeps the function total when no pair exists.
Complexity (this implementation)
time O(n) · space O(1)
Language notes
  • sorted(a) returns a new list (O(n) memory); a.sort() sorts in place — use the latter if the caller allows mutation.
  • Type hint list[int] needs Python 3.9+; use List[int] from typing on older versions.
  • enumerate is unnecessary here because both pointers are explicit indices.
Common mistakes in this language
  • Writing while l <= r and matching an element with itself.
  • Sorting the input when the problem wants original indices back.
  • Reaching for a dict (classic Two Sum) when the sorted guarantee makes O(1) space possible.
Language differences that matter here
  • Overflow on a[l] + a[r]: C++ int overflow is undefined behaviour (use long long); JavaScript/TypeScript are exact only up to 2^53; Python integers never overflow.
  • Empty input: C++ a.size() - 1 is size_t and wraps; JS/TS/Python produce -1 and the while (l < r) guard handles it.
  • Sorting first: JS/TS sort() compares as strings by default; C++ std::sort and Python sort() compare numerically.
  • Return shape: C++ returns a heap-allocated vector<int>; TS can express the fixed tuple [number, number]; Python would normally return a tuple.

Complexity

Best
O(1)
Average
O(n)
Worst
O(n)
Space
O(1)

Plus O(n log n) if the input must be sorted first. Three Sum wraps this in an outer loop for O(n²).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Sorted array and a pair/triple condition on values (sum, difference, closeness to a target).
  • Problems with a two-sided geometric structure: palindromes, reversing, containers, trapping rain water.
  • When O(1) extra space is required and a hash-map solution would use O(n).
  • Counting pairs satisfying an inequality — when a[l] + a[r] < k, all r - l pairs (l, j) count at once.
Avoid it when
  • Unsorted input where original indices must be returned and sorting is not allowed — use a Hash Map (classic Two Sum).
  • The decision rule is not monotone: if a larger a[r] could make the condition *either* more or less satisfied, dropping an end is unsafe.
  • Linked lists without random access to the tail — the same idea needs an O(n) reversal or a stack.
  • When the pair condition is on indices (subarray, window) rather than values — that is Sliding Window (Variable Size) or Two Pointers (Same Direction).

Alternatives

Hash MapBinary SearchSliding Window (Variable Size)Two Pointers (Same Direction)
Compare: Sliding Window vs Two Pointers

Common mistakes

  • Forgetting to sort, or sorting when the answer must be original indices.
  • Using while l <= r for a pair problem — pairs the same element with itself.
  • In Three Sum, not skipping duplicate values after finding a triple, producing repeated answers.
  • Moving the *taller* wall in the container problem "because it looks promising" — that direction can only lose area.
  • Integer overflow on a[l] + a[r] in fixed-width languages when values approach 2^31.

Interview patterns

  • Two Sum II, then Three Sum / Four Sum by fixing one element and running two pointers on the rest.
  • Three Sum Closest: track the minimum |sum - target| while squeezing.
  • Container With Most Water and Trapping Rain Water (opposite pointers plus running left/right maxima).
  • Valid Palindrome / palindrome with at most one deletion — on mismatch, try skipping either side.
  • Count pairs with sum less than k: when a[l] + a[r] < k, add r - l and advance l.
  • Squares of a sorted array: fill the output from the back with whichever end has larger absolute value.
Interview questions on this
Mock interviews

Example problems

3SummediumContainer With Most WatermediumTwo Sum II — Sorted InputeasyTrapping Rain Waterhard