Two Pointers

Use two index markers instead of two nested loops.

The idea

Imagine two people walking toward each other along a sorted row of numbered stones, one from each end. You want two stones that add up to a target. If the sum is too small, the left person steps right to a bigger stone. If it is too big, the right person steps left to a smaller one. Each step rules out a stone for good, so one pass is enough.

The same trick reverses a list in place: swap the two ends, move both markers inward, repeat until they meet.

Watch it work

Try it

Common mistakes

How fast is it?

Time: O(n) – the pointers only ever move inward, so each item is looked at at most once. A nested-loop version needs O(n²). Space: O(1) – just two integers.