← Two Pointers · guided lesson
Two Pointers
the story
Two pointers from both ends
Every tool here exists because something was too slow or broke without it. Here is what.
Folklore: nobody is credited with inventing it. Indices that start at both ends and walk towards each other already drive the partition step of Tony Hoare's Quicksort (1961), but the interview pattern grew out of everyday practice, not one paper.
why it matters: without it
Every sorted-pair question falls back to O(n²) pair checks, or to O(n) extra memory for a HashSet.
also in this chapter: Read / write pointers (in-place filtering) · Merging two sorted sequences (one pointer each) · Three-way partition (Dutch national flag)
the idea
The idea in 30 seconds
Instead of checking every pair with two nested loops (O(n²)), keep two indices and move them smartly.
Each step, one pointer moves and at least one candidate is thrown away for good — so the work is O(n).
It works when the data has order (sorted, or a clear left/right structure) that tells you which pointer to move.
picture this
A Flipkart price list sorted from cheapest to costliest, and a ₹1,000 gift card for exactly two items. Put one finger on the cheapest item and one on the costliest. Total too low? Move the cheap finger up. Too high? Move the costly finger down. Neither finger ever goes back, so one pass is enough.
watch it
Reverse an array in place
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Reverse an array in place
The simplest opposite-ends pattern. Watch both ends become final after each swap.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Two Sum II — why moving one pointer is safe
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Two Sum II — why moving one pointer is safe
Every move throws away a number that can never be part of the answer (shown grey).
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 7
Read it once. Say it out loud once. Bas.
Opposite ends (left = 0, right = n-1, move inwards): pair sums on sorted arrays, palindromes, reversing, container problems.
key idea 2 of 7
Read it once. Say it out loud once. Bas.
Same direction (read/write or slow/fast): in-place filtering, removing duplicates, partitioning, linked-list cycles.
key idea 3 of 7
Read it once. Say it out loud once. Bas.
One pointer per sequence: two sorted inputs (merge, is-subsequence) — advance the pointer that is behind. To merge in place, fill from the back so nothing is overwritten.
key idea 4 of 7
Read it once. Say it out loud once. Bas.
Why it's correct: every move must discard something that can never be part of the answer. If you can't argue that, two pointers is the wrong tool.
key idea 5 of 7
Read it once. Say it out loud once. Bas.
Sorting first costs O(n log n) — usually still far better than O(n²), but it destroys original indices (store them first if you need them).
key idea 6 of 7
Read it once. Say it out loud once. Bas.
Loop condition is almost always while (left < right) for opposite ends — <= would compare an element with itself.
key idea 7 of 7
Read it once. Say it out loud once. Bas.
Two pointers is the parent of sliding window (same direction, with a window between the pointers).
spot the pattern
When you see this, think this
The array is sorted and you need a pair / triplet with some sum
Opposite-ends pointers
"In place", "O(1) extra space", "remove", "move", "partition"
read/write (same-direction) pointers
Palindrome, reverse, symmetric comparisons
Opposite-ends pointers comparing mirrored characters
Maximize/minimize something that depends on a width between two positions
Start widest, move the limiting side (container pattern)
+4 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Using
left <= rightfor pair problems: the same element would be paired with itself. - Forgetting to skip duplicates in 3Sum — you'll output the same triplet several times.
quick check
One question. No pressure.
Sorted array [1, 3, 5, 9], target 12, left at 1, right at 9. Sum is 10. Which pointer moves?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Valid Palindrome
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
Why is two pointers O(n) and not O(n²)?
Question 1: Why is two pointers O(n) and not O(n²)?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.