# Two Pointers — Part 1: The Pattern

Two pointers replace a nested loop over pairs with **one coordinated scan**. It works whenever the data has an order you can exploit: a sorted array (move the pointer that brings you closer to the goal), or a single pass where one pointer reads and the other writes. Both pointers only move forward (or inward), so the total work is O(n).

![Opposite-end pointers on a sorted array moving inward based on the current sum](diagrams/01-two-pointers.svg)

## 1. The Two Shapes

| Shape | Pointers | Typical problems |
|---|---|---|
| **Opposite ends** | `left = 0`, `right = n − 1`, move inward | pair sum in sorted array, palindromes, container with most water, 3Sum (after sorting) |
| **Same direction** | `slow`/`fast` or `write`/`read`, both move right | remove duplicates, move zeroes, partitioning, merge sorted arrays, linked-list cycle |

## 2. Why Moving One Pointer Is Safe

On a sorted array with `sum = a[left] + a[right]`:

- If `sum < target`, every pair using `a[left]` with any index ≤ right is **also** too small (they're all ≤ a[right]). So `a[left]` can never be part of the answer: discard it with `left += 1`.
- If `sum > target`, symmetrically `a[right]` is too big for every remaining partner: `right -= 1`.

Each step **eliminates a whole row or column** of the n×n pair matrix, which is why n steps are enough. Being able to say this out loud is what interviewers want to hear.

## 3. Templates

```typescript
function pairWithSum(nums: number[], target: number): number[] {
  let left = 0, right = nums.length - 1;
  while (left < right) {
    const s = nums[left] + nums[right];
    if (s === target) return [left, right];
    if (s < target) left++; else right--;
  }
  return [];
}

function compact(nums: number[]): number {
  let write = 0;
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== 0) nums[write++] = nums[read];
  }
  return write;
}
```

```python
def pair_with_sum(nums, target):          # nums is sorted
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        if s < target:
            left += 1                       # need a bigger sum
        else:
            right -= 1                      # need a smaller sum
    return []

def compact(nums):                         # same-direction: read / write pointers
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:                 # keep condition
            nums[write] = nums[read]
            write += 1
    return write                            # new logical length
```

## 4. Recognition Cues

- The input is **sorted**, or sorting it doesn't break the problem (you only need values, not original indices).
- "Find a pair/triplet with property X", "closest sum", "count pairs less than target".
- "In place", "O(1) extra space", "remove/move elements while keeping order".
- Symmetry: palindromes, reversing, comparing from both ends.

If you need **original indices** from an unsorted array, sorting loses them: prefer a hash map (Two Sum) or sort pairs `(value, index)`.

## 5. Variations

- **k-Sum:** sort once, fix the first k − 2 elements with loops, finish with two pointers. 3Sum is O(n²), 4Sum O(n³).
- **Skipping duplicates:** after using a value, advance while the next value is the same, to avoid duplicate triplets.
- **Three pointers (Dutch national flag):** `low`, `mid`, `high` partition an array into three groups in one pass (Sort Colors).
- **Fast and slow on linked lists:** Floyd's cycle detection and finding the middle node (see `08-linked_lists`).

## Common Pitfalls

1. **`left <= right` vs `left < right`:** for pairs, the pointers must not meet (an element can't pair with itself).
2. **Infinite loops:** every branch must move at least one pointer.
3. **Duplicate results in k-Sum:** skip equal values after recording an answer, and when choosing the fixed element.
4. **Sorting when indices are required:** you lose the original positions.
5. **Off-by-one on the write pointer:** `write` is the next free slot, so the kept length is `write`, not `write + 1`.

## Quick Reference

```text
Opposite: l=0, r=n-1; while l<r: s<t → l++ ; s>t → r-- ; else answer
Same-dir: write=0; for read…: if keep(a[read]): a[write]=a[read]; write++
k-Sum: sort; fix first k-2; two pointers on the rest; skip duplicates
Time O(n) after sorting (O(n log n) total if you sort) · Space O(1)
```