Introduction to Two Pointers

Two pointers means keeping two positions (indexes) in an array or string and moving them by a simple rule, instead of checking every pair. There are two common shapes: the pointers start at opposite ends and walk toward each other, or they move in the same direction, one ahead of the other. This lesson covers the first shape; the second comes later in this section.

Here's a question that sounds like it has to try everything: in the sorted list [2, 5, 9, 14, 20, 27, 33], which two numbers add up to 34?

The direct way is to try every pair: 2 with 5, 2 with 9, all the way to 27 with 33. Seven numbers make 21 pairs, which is fine. A hundred thousand numbers make 4,999,950,000 pairs, which is not.

Two pointers answers the same question in at most 99,999 steps, and it never misses the pair. The second half of that sentence is the interesting part. At first it looks impossible: the method skips almost every pair, so how can it be sure the answer wasn't among the ones it skipped?

That question is what this lesson answers. Once you see why skipping is safe, the same reasoning solves Container With Most Water and Trapping Rain Water, and it shows you exactly when two pointers stops working.

In this lesson: the rule for moving the pointers; why a move never throws away the answer, shown as a grid of pairs; the same idea on palindromes, Container With Most Water and Trapping Rain Water; when it doesn't work; and the most common mistakes.

Later: 3Sum, 4Sum and counting pairs are the next lesson. Rewriting an array in place (pointers moving the same way) and walking two arrays at once come later in this section. Fast and slow pointers are taught in the Linked List section. If the list isn't sorted and you need the original positions, use a hash map instead (Hashing section).

Put one pointer on the smallest number and one on the largest. Add them.

• If the sum is too small, move left one step right. Every number to the right of it is bigger, so the sum can only grow.
• If the sum is too big, move right one step left. The sum can only shrink.
• If it matches, you're done.

Here's the full run on [2, 5, 9, 14, 20, 27, 33] with target 34:

Six comparisons. Checking every pair could have taken all 21.

Lay every pair out as a grid. Row i is the left number, column j the right number, and each cell holds their sum. Only the cells above the diagonal matter (i < j). Because the list is sorted, two things are true:

• Along a row, the sums grow as you move right (the right number gets bigger).
• Down a column, the sums grow as you move down (the left number gets bigger).

Now look at what one comparison really tells you. The pointers sit on cell (left, right).

Too small? That cell is the largest sum still available in row left: every other open cell in that row is to its left. If the largest is below the target, the whole row is. So the row goes, all of it, in one comparison. That's what left += 1 means.

Too big? That cell is the smallest sum still available in column right, since every other open cell in it is below. If the smallest is above the target, the whole column is out. That's right -= 1.

So the method never skips a pair without a reason. Each comparison deletes a full row or column of pairs that can't possibly be the answer. Put another way: if some pair (i, j) adds up to the target, then at every step left ≤ i and j ≤ right. The pointers can never walk past it, so they stop only when they find it or meet.

That also gives the running time. Each step deletes a row or a column, and there are only n of those, so the loop runs at most n − 1 times: O(n) time and O(1) extra space.

Below is the pair grid for a list you can change. You choose which pointer moves at each step, and the grid shades the row or column that move throws away.

Try this first: make the wrong move on purpose. When the sum is too small, move right instead. Watch what gets shaded, and whether the answer cell (outlined in green) survives.

Two pointers doesn't always need a sorted array. To check a palindrome, the pointers rely on position instead. A palindrome reads the same both ways, so the first character must match the last, the second must match the second-to-last, and so on. Start at both ends, compare, step both inward.

The move rule is simpler here: on a match, both pointers move, because that pair of characters is checked and done. On a mismatch you can stop. Nothing is sorted, and nothing needs to be.

Two twists you'll meet in practice. Valid Palindrome skips characters that aren't letters or digits and ignores case, so each pointer may jump over several characters before comparing. Valid Palindrome II lets you delete one character. At the first mismatch there are only two choices: skip the left character or skip the right one. Check the rest both ways, and if either reads as a palindrome, the answer is yes.

Container With Most Water gives you wall heights and asks for the two walls that hold the most water between them. The amount is width × the shorter wall. Two walls standing 4 apart, heights 3 and 9, hold 4 × 3 = 12.

Start with the outermost pair, the widest container. Then ask the same question as before: which pointer can move without losing the answer?

Say the left wall is the shorter one. Every other container that uses it is narrower (the right wall can only come inward) and still capped at its height. So none of them can beat the container you just measured, and that wall's whole row of pairs is done. Move it.

Moving the taller wall would be the mistake. Its other containers aren't stuck at the short wall's height, so one of them could hold more, and moving it throws them all away. On heights [3, 9, 4, 8, 2, 7] the correct rule finds 28. Moving the taller wall instead returns 15, and the method quietly misses the best container.

Try it: the same grid, now for walls. Each cell holds the water two walls trap: the row is the left wall, the column the right one. Move the taller wall first and watch what happens to 28.

Trapping Rain Water asks how much rain sits between bars of different heights. The water above bar i is min(tallest bar to its left, tallest bar to its right) − height[i], never less than zero.

The simple way finds both tallest bars for every position, which needs two extra arrays. The two pointers way keeps just two numbers: the tallest bar seen so far from the left end, leftMax, and from the right end, rightMax. Then it asks: which end's water do we already know?

Say leftMax ≤ rightMax. For the bar at left, the real tallest bar to its right is at least rightMax, which is at least leftMax. So the smaller of its two tallest bars is leftMax, and its water is known without looking any further right. Add it, and move left inward. When rightMax is the smaller one, the same reasoning works from the right end.

It's the same question as the shorter wall, asked a new way: one comparison tells you which end can be finished for good. On heights [4, 1, 3, 0, 2, 5, 1, 2] it collects 11 units of water in one pass with O(1) extra space. Checking both tallest bars for every position gives the same 11.

Here's the pair-sum version written carefully in all four languages. The Java and C++ versions add the two numbers as 64-bit values, for a reason the bugs section shows. Each prints the indices it finds for [2, 5, 9, 14, 20, 27, 33] and 34.

Cost: O(n) time, since each step rules out one number, and O(1) extra space. If the input isn't sorted yet, sorting first makes it O(n log n) overall.

Use two pointers from both ends when you see:

• A sorted array (or one you're allowed to sort), and a question about a pair whose sum, difference or other score moves in a known direction.
• Two ends that matter: palindromes, reversing in place, or "from both sides" wording.
• A score built from the two ends, like width × shorter wall, where one end limits the result.
• An O(1) extra space requirement on a pair problem.

And watch for problems that look similar but need something else:

• Unsorted, and the answer needs the original positions. Sorting would scramble them. That's Two Sum, and the tool is a hash map (Hashing section).
• A subarray or substring that must meet a condition. That's a sliding window, the next section: two pointers moving the same way, not toward each other.
• A score that doesn't always grow as you move right, like a product when negative numbers are allowed. The next section of this page shows that one failing.

The whole method rests on one fact: moving left makes the score go up, and moving right makes it go down. Break that, and skipping pairs stops being safe.

Products are the cleanest example. With negative numbers, multiplying by a bigger number can make the product smaller. Here's the same rule applied to products, on [-3, -2, 1, 4] with target 6:

find_product_pair([-3, -2, 1, 4], 6)

It returns None. A check of every pair finds [(-3, -2)]. The pointers walked straight past the answer, because a "too small" product no longer meant the left number was too small.

Two more limits worth knowing:

• Listing every pair that hits the target can't be fast in general. If every number is equal, every pair is an answer, and there are n(n − 1)/2 of them to write out. Counting them is still O(n). That's the next lesson.
• Large numbers overflow. In Java and C++, adding two big ints can wrap around to a negative number, which flips the comparison. The bugs below show it happening.

Each of these comes from misreading why the method works. The outputs are from running the code.

while left <= right in a pair sum. On [3, 5] with target 6 it returns (0, 0), the same index twice, which means 3 + 3. A pair needs two different elements, so the loop must stop when the pointers meet. (In Trapping Rain Water, <= is right, because every bar needs its water counted, including the last one.)

Moving both pointers after a miss. On [1, 5, 6, 8] with target 7 it returns None, but 1 + 6 = 7 is there. A miss only proves something about one end, so only that end may move. (In a palindrome check, a match moves both. That's different: both characters are finished.)

Moving the taller wall. On [3, 9, 4, 8, 2, 7] it returns 15 instead of 28.

32-bit overflow. This Java version adds two ints. On [500000000, 1500000000, 1800000000] with target 2,000,000,000, it prints null, missing 500,000,000 + 1,500,000,000. It goes wrong at the very first step: 500,000,000 + 1,800,000,000 wraps to -1994967296. That looks "too small", so the left pointer moves and throws away the 500,000,000 the answer needed. Use long (Java) or long long (C++) for the sum.

Forgetting what the problem wants back. Two Sum II asks for 1-based positions, so add one to each index. It's not a bug in the method, but it fails the test all the same.

Each problem below trains one version of the idea. They're ordered from easy to hard:

1. Reverse String: swap from both ends toward the middle.
2. Valid Palindrome: compare from both ends, skipping characters that don't count.
3. Squares of a Sorted Array: the largest square is always at one of the two ends.
4. Two Sum II - Input Array Is Sorted: the code template above, with a 1-based answer.
5. Valid Palindrome II: one mismatch allowed, so try both skips.
6. Boats to Save People: pair the heaviest person with the lightest, if they fit.
7. Container With Most Water: move the shorter wall.
8. Trapping Rain Water: fill the lower side first.

When these feel routine, the next lesson fixes one number and runs two pointers on the rest: 3Sum, 4Sum, and counting pairs without listing them.