Lesson 27
Two Pointers
Two indices moving with purpose turn O(n²) pair searches into O(n).
01Why it matters & the intuition
Pair sums, palindromes, merging, deduplicating and container problems collapse from nested loops to one pass once you see the two-pointer pattern.
Think of it like…
Two people start at opposite ends of a sorted bookshelf looking for two books whose prices add to ₹500. If the pair is too expensive, the right person steps left to a cheaper book; too cheap, the left person steps right. Neither ever needs to go back.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- L / R
- pair found
- eliminated
03Key ideas
Opposite ends
On sorted input, left starts at 0 and right at the end. Each comparison lets you safely discard one end.
Same direction (fast/slow)
A slow pointer marks where to write, a fast pointer scans. Removes duplicates in place; on linked lists it finds the middle or detects cycles.
Why it's correct
Each move eliminates candidates that cannot be part of any answer, so skipping them never loses a solution.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
// Sorted input: find indices of two values summing to target.
function pairSum(sorted: number[], target: number): [number, number] | null {
let left = 0;
let right = sorted.length - 1;
while (left < right) {
const sum = sorted[left] + sorted[right];
if (sum === target) return [left, right];
if (sum < target) left++; // need bigger
else right--; // need smaller
}
return null;
}
// Fast/slow: remove duplicates in place, return new length.
function dedupe(sorted: number[]): number {
let write = 0;
for (let read = 0; read < sorted.length; read++) {
if (read === 0 || sorted[read] !== sorted[read - 1]) sorted[write++] = sorted[read];
}
return write;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Pair sum on sorted array | O(n) | O(1) |
| Palindrome check | O(n) | O(1) |
| Brute-force alternative | O(n²) | — |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Valid palindrome
Write is_palindrome(s) returning true if s reads the same forwards and backwards after lowercasing and ignoring every non-alphanumeric character. Use two pointers, no reversed copy.