Two Pointers

What is Two Pointers?

Two Pointers is a way to scan data using two indexes instead of one.

The indexes do not always start at opposite ends. They might both move forward, or one might mark where the next result should be written.

The useful part is the rule that controls them. After looking at the current values, we must know which pointer can move without skipping a possible answer.

It helps to understand arrays, indexes, while loops, and what sorted order gives us. The short version is: use two pointers when two positions give you enough information to safely stop considering part of the input.

The Core Idea: Make One Safe Move

Suppose we have this sorted array:

[1, 3, 4, 5, 7, 10, 11]

We want two numbers whose sum is 18.

We begin with left at 1 and right at 11.

Their sum is 12, which is too small. Which pointer should move?

Moving right would replace 11 with a smaller number, making the sum even smaller. That cannot help.

So we move left to a larger number.

This is the whole idea. We are not guessing which pointer to move. The sorted order proves which move is safe.

It is like choosing two items from a menu sorted by price. If the cheapest and most expensive available items are still under budget, replacing the expensive item with something cheaper cannot reach the budget. The cheaper item must change.

How a Sorted Pair Search Moves

For our target of 18, the search looks like this:

1. 1 + 11 = 12, so move left.
2. 3 + 11 = 14, so move left.
3. 4 + 11 = 15, so move left.
4. 5 + 11 = 16, so move left.
5. 7 + 11 = 18, so we found the pair.

We checked five pairs. A nested-loop solution could check every possible pair.

The Rule You Keep True

You will often hear the word invariant in explanations of this pattern.

An invariant is just a fact that remains true after every pointer move.

For Two Sum II, the invariant is:

If a valid pair still exists, both of its values are somewhere between left and right.

When the current sum is too small, the value at left cannot work with any remaining value. Even the largest remaining value was not enough. Moving left therefore keeps the invariant true.

Different versions of Two Pointers keep different facts true:

• In Remove Duplicates, everything through write is the unique part of the processed array.
• In Merge Sorted Array, everything after write is already in its final position.
• In Valid Palindrome, every character outside the pointers has already been matched.
• In Container With Water, moving the shorter side is the only move that might increase the limiting height.

Why Direction Matters

The two pointers can have several different jobs.

• Opposite ends: Start at the first and last positions, then discard one side after each comparison. Two Sum II uses this shape.
• Both move inward: Compare or swap the two ends, then move both pointers. Valid Palindrome and Rotate Array use this shape.
• Read and write: read examines every value while write advances only when a value belongs in the result. Remove Duplicates uses this shape.
• Work from the back: Compare the largest unread values and fill the final empty position. Merge Sorted Array does this to avoid overwriting values it still needs.
• Fix one value, then use two pointers: 3Sum fixes one number and runs a two-pointer search over the remaining sorted suffix.
• Move the limiting side: Container With Water and Trapping Rain Water move the shorter boundary because that side currently limits the result.

Trapping Rain Water is the one that usually trips us up. Its pointer movement looks similar to Two Sum, but the reason is different. We move the shorter side because the taller side guarantees a boundary, which lets us finish the shorter side without knowing every height in the middle.

Picking the Right Shape

From Rule to Code

1. Decide what each pointer represents.
2. Put each pointer at the position required by that job.
3. State the fact that must remain true after every move.
4. Inspect the current values and process the answer if you found one.
5. Move only the pointer whose movement is justified by your rule.

The loop finishes because at least one pointer moves toward the end of its allowed range on every iteration.

A single two-pointer pass is usually O(n). 3Sum is O(n²) because it repeats that pass for different fixed values, and sorting may add O(n log n) before the scan.