Two Pointers
Two indices that move toward each other or in the same direction. They replace a nested loop with a single O(n) pass on sorted arrays and strings.
The idea
Instead of checking every pair (i, j) with two loops (O(n²)), keep two indices and move one of them each step based on what you see. Every move rules out a whole set of pairs, so the total work is O(n).
Two common shapes:
- Opposite ends:
lo = 0,hi = n − 1, moving inward. Used for pair sums in a sorted array, palindromes, container with most water and trapping rain water. - Same direction (read / write): a fast “read” pointer scans while a slow “write” pointer marks where the next kept element goes. Used to remove duplicates, move zeroes, partition (Dutch flag) and merge sorted arrays.
Why it is correct (pair sum)
The array is sorted. If a[lo] + a[hi] < target, then a[lo] paired with any element left of hi is even smaller, so a[lo] can never be part of the answer and it is safe to do lo++. The symmetric argument justifies hi--.
Recognise it
- The input is sorted (or you can sort it) and you need pairs or triplets
- “In place”, “O(1) extra space”
- Palindromes or reversing
- 3Sum / 4Sum: fix one element, then two pointers on the rest
Code template
# Opposite ends: pair with sum = target in a sorted array
def pair_sum(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 None
# Same direction: remove duplicates in place from a sorted array
def dedupe(a):
w = 0
for r in range(len(a)):
if r == 0 or a[r] != a[r - 1]:
a[w] = a[r]
w += 1
return w # new length// Opposite ends: pair with sum = target in a sorted array
int[] pairSum(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) return new int[]{lo, hi};
if (s < target) lo++; else hi--;
}
return null;
}
// Same direction: remove duplicates in place from a sorted array
int dedupe(int[] a) {
int w = 0;
for (int r = 0; r < a.length; r++)
if (r == 0 || a[r] != a[r - 1]) a[w++] = a[r];
return w;
}// Opposite ends: pair with sum = target in a sorted array
pair<int, int> pairSum(const vector<int>& a, int target) {
int lo = 0, hi = (int)a.size() - 1;
while (lo < hi) {
int s = a[lo] + a[hi];
if (s == target) return {lo, hi};
if (s < target) lo++; else hi--;
}
return {-1, -1};
}
// Same direction: remove duplicates in place from a sorted array
int dedupe(vector<int>& a) {
int w = 0;
for (int r = 0; r < (int)a.size(); r++)
if (r == 0 || a[r] != a[r - 1]) a[w++] = a[r];
return w;
}// Opposite ends: pair with sum = target in a sorted array
function pairSum(a, target) {
let lo = 0, hi = a.length - 1;
while (lo < hi) {
const s = a[lo] + a[hi];
if (s === target) return [lo, hi];
if (s < target) lo++; else hi--;
}
return null;
}
// Same direction: remove duplicates in place from a sorted array
function dedupe(a) {
let w = 0;
for (let r = 0; r < a.length; r++) if (r === 0 || a[r] !== a[r - 1]) a[w++] = a[r];
return w;
}Complexity
O(n) time and O(1) space for one pass. Sorting first costs O(n log n). 3Sum is O(n²): n choices for the first element, then O(n) two pointers.
Practise this pattern (6 problems)
Each problem has a statement, hints, approaches, solutions in 4 languages and a code runner. Solve them in order: easy first.
| # | Problem | Difficulty | |
|---|---|---|---|
| 10 | Valid Palindrome | Easy | |
| 11 | Move Zeroes | Easy | |
| 12 | Two Sum II (Sorted Input) | Medium | |
| 13 | 3Sum | Medium | |
| 14 | Container With Most Water | Medium | |
| 15 | Trapping Rain Water | Hard |
Common mistakes
- Using two pointers on an unsorted array for a pair sum: sort first, or use a hash map.
while lo <= hiversuswhile lo < hi: for pairs you need two different positions, so use<.- Forgetting to skip duplicates in 3Sum (gives repeated triplets).