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.
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental 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.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Each step throws away one end. The dimmed items can never be part of the answer.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#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";
}1 + 14 = 15 no pair sums to 2 14 11 8 6 4 3 1
05Complexity
| brute force (all pairs) | O(n²) |
|---|---|
| two pointers on sorted data | O(n) |
| sort first, then two pointers | O(n log n) |
| Extra space | O(1) |
The opposite-ends version needs sorted data so you know which pointer to move.
06Watch
Two Pointers in 7 minutes
Why this one: The pattern and its variants in 7 minutes.
Two Sum II (Leetcode 167)
Why this one: NeetCode solves Two Sum II, the textbook two-pointer problem.
Original class slides (Python, by the course's lecture authors):Two Pointers
07Exam lens
Likely questions
- Why does the pair-sum algorithm only work on sorted input?
- Why is moving
lright the only sensible move when the sum is too small? - Name three problems solved with two pointers.
Common mistakes
- Using
l <= rand pairing an item with itself. - Running opposite-end two pointers on unsorted data.
- Moving both pointers at once and skipping valid pairs.
08Quick check
09Practice
🟢 Trace by hand
Find a pair summing to 10 in 1 2 4 5 7 9 with two pointers. List each (l, r, sum).
Show answer
- 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.
🔴 Solve problems
Hint
This page's code, returning 1-based indices.
Hint
Opposite-end pointers, skipping non-alphanumeric characters.
Hint
Start wide. Always move the shorter wall; moving the taller one can never help.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.