Two Pointers: Stop Looking at the Same Elements Twice

1 · The problem$18 for exactly two things

Mom hands over eighteen dollars with one rule: buy exactly two things. And to spend all of it, those two things have to cost exactly $18 together.

In front of the house, mom stands at the door; between them a $18 chip and the rule 2 THINGS = $18 — The budget, and the rule: two items, $18 exactly.

At the store, the items stand in a row on the shelf, each with its price — and the prices are already in order, smallest to biggest: $2, $3, $4, $7, $11, $15, $20. Which two add up to eighteen?

The narrator under the store's shelf; on it seven cartons priced $2, $3, $4, $7, $11, $15, $20, in order — Seven prices, sorted. Somewhere in them is a pair that makes 18.

Stated without the store: given a list of numbers sorted from smallest to biggest and a target, find the two positions whose numbers add up to the target. There is exactly one such pair, you can't use the same position twice, the positions are counted from 1, and you may only use a constant amount of extra memory.

2 · The obvious ideaThe obvious way: every pair

Try every pair. Take the $2 and try it with everything after it: 2 + 3, 2 + 4, 2 + 7, 2 + 11, 2 + 15, 2 + 20. None of them is 18. Next: take the $3 and try everything after it. Then the $4…

Under the shelf, red arcs join the $2 carton to the others while the narrator walks off, a pile of crossed-out sums growing at his feet — Every pair with $2, tried and crossed out one by one.

In code, two loops, one inside the other:

def two_sum_every_pair(numbers, target):    for i in range(len(numbers)):        for j in range(i + 1, len(numbers)):            if numbers[i] + numbers[j] == target:                return [i + 1, j + 1]

It works. On this shelf it finds $3 + $15 on its tenth check. But look at what it does along the way: the $15 is picked up, added to something, and put back again and again; so is the $20. You are checking the same numbers over and over.

A tangle of red arcs under the shelf and a tall pile of crossed-out sums; the narrator stands beside it, a spiral in his thought bubble — The same prices, picked up again with every new partner.

With n prices there are n(n − 1) / 2 pairs — 21 for seven prices, about 5,000 for a hundred, about 50 million for ten thousand. That is O(n²): double the shelf and the work goes up four times.

3 · The observationBut wait — the prices are sorted

The every-pair loop would work just as well on a shuffled shelf. It never uses the one thing the problem gave us for free: the order. Maybe the order itself can help.

The narrator crouched beside the pile of crossed-out sums under the shelf's tangle of arcs — The question to ask of any problem: what did they give me that I am not using?

In a sorted list, the smallest number is at the left end and the biggest at the right end. If you add those two, you know something about every other pair: nothing can be smaller than the left end, nothing bigger than the right end.

4 · The discoveryStart at both ends

So instead of checking everything, start from the two ends: one hand — a left pointer — on the smallest price, the other — a right pointer — on the biggest. In the video he stands under the cheapest carton and calls a friend to stand under the dearest: the two of them are the pointers.

The narrator stands under the $2 carton with the LEFT arrow over it; his friend stands under the $20 at the other end — Left on the smallest, right on the biggest — the two of them are the pointers.

First try: 2 + 20 = 22. Too big. We need a smaller sum, and there is only one way to get one: the right pointer moves left, to a smaller price.

LEFT over $2, RIGHT over $20, and between the two students the sum 2 + 20 = 22 — 22 is over 18. The right end has to come in.

Second try: 2 + 15 = 17. Too small this time. We need a bigger sum, so the left pointer moves right, to a bigger price.

The $20 faded, RIGHT now over $15, and the sum 2 + 15 = 17 — 17 is under 18. The left end has to come in.

Third try: 3 + 15 = 18. Exactly eighteen. Three checks.

The $2 and $20 faded, LEFT over $3, RIGHT over $15, the sum 3 + 15 = 18 and the badge FOUND — $3 + $15 = $18, found on the third check. The every-pair loop needed ten.

5 · The reasoningWhy each move is safe

Three checks instead of ten is nice, but it is only worth anything if we can't skip past the answer. Look at what each move throws away.

The tag 22 · TOO BIG between the students; the $20 faded and the RIGHT arrow moved in to $15 — Too big: move the right pointer left.

Too big. 2 + 20 = 22 is over the target. The $2 is the smallest price there is, so the $20 paired with anything else is bigger still. The $20 cannot be part of the answer at all — drop it. That is what moving the right pointer means.

The tag 17 · TOO SMALL; the $2 faded and the LEFT arrow moved in to $3 — Too small: move the left pointer right.

Too small. 2 + 15 = 17 is under the target, and the $15 is the biggest price still in play. So the $2 paired with anything that is left is smaller still. The $2 cannot be part of the answer — drop it. That is what moving the left pointer means.

The key idea

Because the numbers are sorted, every check tells you something about a whole group of pairs, not just the one you checked. Too big means the right number is useless with everything that is left; too small means the left number is. Either way one number leaves for good, and the answer is still between the pointers.

6 · The proofWhy it never misses: the pair grid

Draw every pair the every-pair loop would check as a grid: one row per left number, one column per right number. Only the squares above the diagonal are real pairs — 21 of them for seven prices.

On the monitor, a triangular grid of the 21 pairs; the whole column under 20 is crossed out in red, labelled 6 PAIRS — 22 was too big, so every pair with the 20 is too big: the whole column goes, six pairs with one check.

The first check, 2 + 20, is the corner of the grid. Too big: the whole column of the 20 is crossed out — six pairs gone, with one check. The second check, 2 + 15, is the corner of what is left. Too small: the whole row of the 2 goes — five more. The third check is the answer.

The grid with the 20's column (6 PAIRS) and the 2's row (5 PAIRS) crossed out, the pair 3 and 15 lit yellow; 3 CHECKS, BRUTE FORCE: 10 — One column, one row, then the answer. Three checks against the every-pair loop's ten.

That is the whole proof. The two pointers always look at the top-right corner of the pairs not yet ruled out, and that corner is special: it is the biggest pair in its row and the smallest in its column. Every check removes a full row or a full column of the remaining grid, and never a square that could still be the answer. With n numbers there are only n − 1 rows and columns to remove, so the search takes at most n − 1 checks.

7 · The costWhat it costs

On a monitor, two panels: a tangle of arcs over the prices marked O(N²) in red, and the two pointers alone marked O(N) in green — Each pointer only moves one way, so the work grows with the length of the list, not its square.

Time: O(n). The left pointer only moves right, the right pointer only moves left, and they stop when they meet: together they take at most n − 1 steps, one check per step. Space: O(1). Two indices and a sum, whatever the size of the list.

Every pair · 10,000 numbers≈ 50,000,000checks

Two pointers · 10,000 numbers≤ 9,999checks

If the list were not sorted, the usual fast answer is a hash map: walk once, and for each number ask "have I already seen 18 minus this?". That is also O(n) time, but O(n) memory for the map. Here, the sorted order does the remembering for us — that is why the memory can be constant.

8 · The nameThis is two pointers

Only now the name: two pointers. Two positions in the same list, each moving in one direction, every move decided by what the last check said.

A card on the monitor: TWO POINTERS — START AT BOTH ENDS, CHECK THE SUM, TOO BIG? MOVE RIGHT ←, TOO SMALL? MOVE LEFT →, FOUND? STOP — The whole algorithm fits on a card.

Start at both ends
Left on the smallest, right on the biggest.
Check the sum
Add the two numbers you are pointing at.
Too big? Move right in
The biggest number can't be used. Drop it.
Too small? Move left in
The smallest number can't be used. Drop it.
Found it? Stop
Return the two positions.

9 · The codeThe code, one move per line

Nothing new happens in the code: the same moves as in the store, written down. The function gets the sorted numbers and the target.

class Solution:    def twoSum(self, numbers, target):

Start at both ends

Left points at the first position, right at the last.

class Solution:    def twoSum(self, numbers, target):        left, right = 0, len(numbers) - 1

Keep going while left is before right

class Solution:    def twoSum(self, numbers, target):        left, right = 0, len(numbers) - 1         while left < right:

Strictly less than, not less-or-equal. If the pointers meet, both point at the same position, and adding it to itself would use the same number twice — which the problem forbids.

LEFT and RIGHT both over the $7 carton, the others faded, SAME NUMBER TWICE in red; on the monitor the line while left < right is lit — If left and right meet, there is no pair left to try.

Add the two numbers

        while left < right:            total = numbers[left] + numbers[right]

Found it? Stop

If the total is the target, return both positions — plus one each, because the problem counts positions from 1, while Python's indices start at 0.

        while left < right:            total = numbers[left] + numbers[right]             if total == target:                return [left + 1, right + 1]

Position numbers 1 to 7 under the cartons; on the monitor the lines if total == target and return [left + 1, right + 1] are lit — Index 1 and index 5 in Python are positions 2 and 6 in the answer.

Too big? Move the right pointer in

        while left < right:            total = numbers[left] + numbers[right]             if total == target:                return [left + 1, right + 1]            elif total > target:                right -= 1

Too small? Move the left pointer in

Otherwise the total is too small (it isn't equal, and it isn't bigger).

        while left < right:            total = numbers[left] + numbers[right]             if total == target:                return [left + 1, right + 1]            elif total > target:                right -= 1            else:                left += 1

The whole thing

class Solution:    def twoSum(self, numbers, target):        left, right = 0, len(numbers) - 1         while left < right:            total = numbers[left] + numbers[right]             if total == target:                return [left + 1, right + 1]            elif total > target:                right -= 1            else:                left += 1

Nine lines inside the function, and every lit one is a move from the store. Run it on the shelf:

Check	left	right	total	Verdict
1	0 → $2	6 → $20	22	too big: `right -= 1`
2	0 → $2	5 → $15	17	too small: `left += 1`
3	1 → $3	5 → $15	18	found: `return [2, 6]`

LEFT over $2, RIGHT over $20, 2 + 20 = 22 TOO BIG over the monitor, where the line elif total > target is lit — The first check of the real run.

LEFT over $3, RIGHT over $15, 3 + 15 = 18 FOUND, and a starburst [2, 6] on the monitor — The third check returns [2, 6].

Two more runs to check yourself against: on [2, 7, 11, 15] with target 9 it returns [1, 2] after one check, and on [-1, 0] with target -1 it returns [1, 2] — negative numbers change nothing, only the order matters.

In the store	In the code
Start at both ends	`left, right = 0, len(numbers) - 1`
Add the two prices	`total = numbers[left] + numbers[right]`
Eighteen: stop	`return [left + 1, right + 1]`
Too big: right moves in	`right -= 1`
Too small: left moves in	`left += 1`

A STORY / PYTHON table: start at both ends, add the two prices, eighteen: stop, too big: right moves in, too small: left moves in — each beside its line of code — The same table as the video ends its code part on: every line is a move from the store.

10 · The trapsThree mistakes to watch for

Three cards on the monitor under 3 MISTAKES: while left <= right → SAME NUMBER TWICE; return [left, right] → WRONG POSITIONS; elif total > target: left += 1 → WALKS PAST THE ANSWER — Each one is a single character or a single word away from the right program.

while left <= right lets the pointers meet and add a number to itself. On [3, 4] with target 6, it would answer 3 + 3.
return [left, right] forgets the plus one: the answer is off by one position on both sides.
Moving the wrong pointer. On "too big", left += 1 makes the sum bigger. On the shelf it drops the $2 — fine — then sits on 3 + 20 = 23, too big again, drops the $3, and walks straight past the answer.

11 · Try itYour own numbers

Watch the pointers and the pair grid

The Python above, translated to run in your browser. Each check is a square of the grid; a "too big" crosses out its column, a "too small" its row. Change the numbers (they are sorted for you) and the target.

Numbers Target

Press Step.

checks 0pairs ruled out 0pairs in all 0every-pair loop would need 0

Things to try: a target no pair can make (the pointers meet and the loop ends — there would be no answer to return); a target made by the two smallest numbers (watch the right pointer walk all the way in); a long list, to see the gap between the two counters grow.

12 · The bigger ideaNot just for two numbers

The idea isn't really about finding two numbers. It is about ordered data: whenever things are sorted, two positions moving one way each can often walk through them without ever going back. Two sorted lists of user IDs, and you want the ones in both? Put a pointer at the start of each list; whichever points at the smaller ID moves on; when they match, you've found one.

On the monitor two sorted rows of user numbers, USERS A 102 105 108 112 120 and USERS B 101 105 108 115 120, with 105 and 108 lit in both — Two sorted lists, two pointers, one pass: the common entries without comparing every pair.

The question to ask

Whenever you see two nested loops over the same list, ask: am I looking at the same elements twice? If the data is sorted — or you can afford to sort it — one check can often rule out a whole group, and one pass replaces the nest.

13 · PracticeFour problems, same shape

Don't copy the code. For each one, find the moves first: where do the pointers start, and what makes each one move?

Warm-upTwo sum on a sorted list, from scratch
Close this page and write it. Then add a counter and check that it never needs more than n − 1 checks.
PracticeValid palindrome
Does a sentence read the same backwards, ignoring spaces and punctuation? Two pointers at the ends again — but there is no sum. What decides the move?
VariationContainer with most water
Vertical lines of different heights; which two hold the most water between them? Start at both ends. Which pointer can't possibly help any more — and why is it the shorter line?
ChallengeThree numbers that sum to zero
List every set of three numbers in a list that adds up to zero, without repeats. Hint: sort first, fix one number, and the other two are a problem you just solved.

Another way to stop repeating work — dynamic programming →

Two pointers avoid looking at the same elements twice. Dynamic programming avoids solving the same question twice: a street of houses, two neighbours you can't both rob, and the one number per house you need to remember.

If you understand why the pointer moves, you can write the code.

Two pointers — stop looking at the same elements twice

Watch the video version