The Two-Pointer Idea

Two Pointers, lesson 1 of 3

The Two-Pointer Idea

Squeeze a sorted array from both ends and learn why each move is safe.

12 min, 0 of 3 activities solved

Getting Python ready… examples can run in a moment.

Lots of array problems ask about pairs: two numbers that add up to a target, two walls that hold the most water, two ends of a string that should match. The obvious answer is a nested loop that tries every pair: O(n²).

Two pointers replaces that with two indices, usually called lo and hi. Each step moves one of them, and they never move backwards. Together they take at most n steps, so the whole scan is O(n) with O(1) extra space.

The classic: a sorted list and a target sum. Start with one pointer at each end and look at the sum:

too big? move hi left (to a smaller number)
too small? move lo right (to a bigger number)
equal? done

nums = [1, 3, 4, 6, 8, 11]   target = 10

lo=1  hi=11   12  too big   -> hi -= 1
lo=1  hi=8     9  too small -> lo += 1
lo=3  hi=8    11  too big   -> hi -= 1
lo=3  hi=6     9  too small -> lo += 1
lo=4  hi=6    10  found it!

Example

Brute force vs two pointers

Same answer, but the nested loop needs about half a million checks while the pointers need about a thousand. Try a target that doesn't exist, like 3: the brute force checks every pair.

Why is it safe to throw a number away? This is the part interviewers love to ask about.

Say nums[lo] + nums[hi] < target. nums[hi] is the largest value still in play, so nums[lo] plus any other remaining value is even smaller, and also misses the target. nums[lo] can't be part of any answer, so dropping it (lo += 1) loses nothing. The "too big" case is the mirror image: nums[hi] plus the smallest remaining value is already too big, so drop nums[hi].

Every step eliminates one candidate that provably can't be in the answer. That elimination argument is the heart of the pattern; you'll reuse it for Container With Most Water and Trapping Rain Water.

Quiz

What does this print?

5 15

9 11

2 15

9 15

Quiz

The list is sorted and nums[lo] + nums[hi] > target. Why is it safe to move hi left?

nums[hi] plus even the smallest remaining value is too big, so nums[hi] can't be in any answer

Because hi is always bigger than lo

Because moving lo would skip the answer, so we must move something else

It isn't always safe; we just hope the answer is further left

The same "one at each end, walk inward" shape works without any sums: anything about symmetry. Checking a palindrome compares s[lo] with s[hi]; reversing a list in place swaps them. You stop when the pointers meet in the middle.

Example

Reverse in place

lo < hi (not <=) is the right stop: when they meet on the middle element there's nothing to swap. Try an even-length word too.

Exercise

Count pairs within budget

prices is sorted ascending. Write count_pairs(prices, budget) that returns how many pairs i < j have prices[i] + prices[j] <= budget. Do it in one O(n) two-pointer pass.

count_pairs([1, 2, 3, 4, 5], 6) is 6: (1,2) (1,3) (1,4) (1,5) (2,3) (2,4).