Pattern7 min read

Two Pointers

Two indices moving from opposite ends — turns sorted-array search problems into O(n).

arraystwo-pointers

Intro

When the array is sorted (or can be sorted), 'two pointers from opposite ends' is the cheapest tool in the box. It removes a dimension from the search space at every step, giving O(n) where naive nested loops give O(n²).

Key insight

If the current pair is too small / too large, only one of the two pointers can possibly fix it — move that one.

Approach

1Sort the array (or skip if already sorted).
2Place left = 0, right = n - 1.
3Compute the candidate answer from arr[left] and arr[right].
4If too small, increment left; if too large, decrement right; if equal, record and move both.

Example

Input

arr = [-2, 1, 2, 4, 7, 11], target = 13

Output

(2, 11)

Trace

left=0 (-2), right=5 (11) → sum 9, too small → left++
left=1 (1), right=5 (11) → sum 12 → left++
left=2 (2), right=5 (11) → sum 13 ✓

Complexity

Time

O(n) after the O(n log n) sort

Space

O(1)

Code

Snippetjava

int[] twoSumSorted(int[] a, int target) {
    int l = 0, r = a.length - 1;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == target) return new int[]{l, r};
        if (s < target) l++; else r--;
    }
    return new int[]{-1, -1};
}

Pitfalls

Forgetting to dedupe when scanning all triplets (3Sum) — leads to repeated answers.
Reading two-pointers as 'fast & slow' — those are different patterns.
Using two-pointers on an unsorted array without justification.

Variants & follow-ups

3Sum (LC 15)
Container With Most Water (LC 11)
Trapping Rain Water (LC 42)