# LU.1 Two Pointers

> Two indices that move toward each other (or in the same direction) to replace an O(n²) pair search with one O(n) pass.

Chapter: Level Up: Problem Patterns · ~40 min · medium · optional, not on the exam
URL: https://dsa.fetehadin.com/learn/two-pointers

## Mental model

Two people search a **sorted bookshelf** for two books whose prices add up to 15 birr. One starts at the cheap end, the other at the expensive end. Too expensive? The person at the expensive end steps in. Too cheap? The person at the cheap end steps in. They never need to go back.

### Why it works

The array is sorted. If `a[l] + a[r]` is **too small**, then `a[l]` paired with anything left of `r` is even smaller, so `a[l]` is useless: move `l` right. If it is **too big**, `a[r]` is useless: move `r` left. Every step discards one item, so the search is **O(n)** instead of checking all **n²** pairs.

### Two flavours

- **Opposite ends** (`l = 0`, `r = n − 1`, move inward): pair sums, reversing, palindromes, container with most water.
- **Same direction** (a slow write pointer and a fast read pointer): removing duplicates in place, moving zeros. Fast & slow pointers on linked lists are the same idea.

> Built on Chapter 3 (sorting and binary search thinking). Not on the exam.

## C++ code: two-pointers.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

bool pairSum(const vector<int>& a, int target) {     // a must be sorted
    int l = 0, r = a.size() - 1;
    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == target) { cout << a[l] << " + " << a[r] << " = " << target << "\n"; return true; }
        if (sum < target) l++;                         // need a bigger sum
        else r--;                                      // need a smaller sum
    }
    cout << "no pair sums to " << target << "\n";
    return false;
}

void reverseInPlace(vector<int>& a) {
    for (int l = 0, r = a.size() - 1; l < r; l++, r--) swap(a[l], a[r]);
}

int main() {
    vector<int> a = {1, 3, 4, 6, 8, 11, 14};
    pairSum(a, 15);
    pairSum(a, 2);
    reverseInPlace(a);
    for (int x : a) cout << x << " ";
    cout << "\n";
}
```

Expected output:

```text
1 + 14 = 15
no pair sums to 2
14 11 8 6 4 3 1
```

## Complexity

| Case | Cost |
| --- | --- |
| brute force (all pairs) | O(n²) |
| two pointers on sorted data | O(n) |
| sort first, then two pointers | O(n log n) |

Space: O(1)

The opposite-ends version needs **sorted** data so you know which pointer to move.

## Videos

- [Two Pointers in 7 minutes](https://youtu.be/QzZ7nmouLTI) (AlgoMasterIO): The pattern and its variants in 7 minutes.
- [Two Sum II (Leetcode 167)](https://youtu.be/cQ1Oz4ckceM) (NeetCode): NeetCode solves Two Sum II, the textbook two-pointer problem.

## Exam lens

Likely questions:

- Why does the pair-sum algorithm only work on sorted input?
- Why is moving `l` right the only sensible move when the sum is too small?
- Name three problems solved with two pointers.

Common mistakes:

- Using `l <= r` and pairing an item with itself.
- Running opposite-end two pointers on unsorted data.
- Moving both pointers at once and skipping valid pairs.

## Quick check

1. Array `1 3 4 6 8 11 14`, target 15. First pair checked?
   A. 1 + 3
   B. 1 + 14
   C. 6 + 8
   D. 3 + 11
   Answer: B. Start at both ends.

2. sum < target. Which pointer moves?
   A. r moves left
   B. l moves right
   C. both
   D. neither
   Answer: B. Only a bigger left value can increase the sum.

3. Time complexity of the two-pointer pair search?
   A. O(1)
   B. O(n)
   C. O(n log n)
   D. O(n²)
   Answer: B. Each step moves one pointer, so at most n steps.

## Practice

**Trace by hand.** Find a pair summing to 10 in `1 2 4 5 7 9` with two pointers. List each (l, r, sum).

Solution:

- l=0, r=5: 1 + 9 = 10 → **found** on the first step.

Try target 11: (0,5) 10 < 11 → l=1 · (1,5) 2 + 9 = 11 → found.


**Implement it.** Check whether a string is a palindrome, skipping non-letters, using two pointers.

Hint: `l` from the start, `r` from the end. Skip characters that are not `isalnum`, compare `tolower`, move both inward.

**Problems:**

- [Two Sum II - Input Array Is Sorted](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/) (medium). Hint: This page's code, returning 1-based indices.
- [Valid Palindrome](https://leetcode.com/problems/valid-palindrome/) (easy). Hint: Opposite-end pointers, skipping non-alphanumeric characters.
- [Container With Most Water](https://leetcode.com/problems/container-with-most-water/) (medium). Hint: Start wide. Always move the shorter wall; moving the taller one can never help.

## Mastery checklist

- [ ] I can explain why two pointers turns O(n²) into O(n).
- [ ] I can solve pair-sum on a sorted array.
- [ ] I can recognise when a problem fits the pattern.