# Two Pointers — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/two-pointers

> Two indices moving through a sequence to replace a nested loop with a single pass.

## Converging or chasing

**Opposite ends**: `left` and `right` move toward each other (sorted two-sum, palindrome, container with most water). **Same direction**: a slow and fast pointer (remove duplicates in place, cycle detection). Turns `O(n^2)` into `O(n)`.

## Sorted two-sum

If the sum is too small, only moving `left` up can help; too big, only moving `right` down.

```python
def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return [lo, hi]
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []
```

**Quiz:** The opposite-ends two-pointer trick needs the array to be...

- [x] Sorted
- [ ] All positive
- [ ] Even length

*Answer:* Sorted. Sorted order is what lets you decide which pointer to move from the current sum.