What is the two-pointer technique?

Question

Accepted Answer

The **two-pointer** technique uses two indices that move through a sequence to solve problems in a single pass — turning many O(n²) brute-force solutions into **O(n)**.

## The idea

Keep two pointers (often at the ends, or one slow and one fast) and move them based on a condition, shrinking the work without rescanning.

## Example: pair summing to a target in a sorted array

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## Complexity

- **Time:** O(n). **Space:** O(1).

## When to use / pitfalls

Great for **sorted arrays**, palindrome checks, reversing, and removing duplicates in place. The array often must be sorted for the converging-pointer variant. Be careful with pointer bounds and the loop condition (`lo < hi`).

## Why it matters

Two pointers is one of the highest-leverage interview patterns: it collapses nested loops into a clean linear scan.

It teaches you to exploit structure (like sortedness) instead of brute force.

The same idea powers merging, partitioning, and the merge step of merge sort.