Two Pointers

What is two pointers?

Two pointers is an algorithmic technique that uses two index variables to scan an array, eliminating the need for a nested loop. Instead of O(n²), most problems reduce to O(n).

The key insight: if you are searching for a pair satisfying some condition in a sorted array, you can start one pointer at each end. If the current pair's value is too small, move the left pointer right (increasing the sum); if too large, move the right pointer left (decreasing it). Each step eliminates one pointer position from consideration - you have seen everything that pointer could pair with, given the current state of the other pointer.

Two pointers appears in two main configurations. The opposite-ends (converging) variant starts left at index 0 and right at the last index and moves them toward each other. The same-direction variant has both pointers start near the left and move forward, but at different speeds or with different advancement conditions - used for in-place element removal and partitioning.

Two pointers is not the same as binary search. Binary search halves the space at each step without examining every element. Two pointers examines every element in a structured sweep - it trades the logarithmic property for the ability to maintain a running relationship between two positions.

Core operations

Key patterns

Opposite-ends (sorted array pair sum)

One pointer at each end, move whichever pushes the running sum toward the target.

The problem shape

Given a sorted array, find a pair (or triplet) satisfying a sum condition. The result is the pair of indices, values, or a boolean. The constraint is O(n) - the brute-force double loop is O(n²).

The key insight

The loop runs while left < right, never <=, because a valid pair never reuses one element. Each step moves exactly one pointer inward: if the sum is too small, advance left (grows the sum); if too large, advance right (shrinks it). This is valid only because the array is sorted - moving left rightward can only grow the sum and moving right leftward can only shrink it. Each move provably eliminates one pointer position: everything it could have paired with has already been considered. The two pointers only ever travel toward each other, taking at most n steps total - O(n) time, O(1) space.

Example: pair summing to a target in a sorted array. Given [3, 8, 12, 19] and target 11, the very first probe 3 + 19 = 22 overshoots, which immediately kills index 3 as a partner for 3 and pulls right inward. Two more comparisons and the pointers settle on 3 + 8, returning indices [0, 1]. The walkthrough below traces exactly that input.

Solution walkthrough: Two Sum Sorted

Walk [3, 8, 12, 19] with target 11:

• left=0 (3), right=3 (19): sum 22 > 11, move right to 2.
• left=0 (3), right=2 (12): sum 15 > 11, move right to 1.
• left=0 (3), right=1 (8): sum 11 == 11. Return [0, 1].

No match would return [] - the pointers met without finding the target.

Same-direction (in-place removal)

Two pointers move forward together: slow marks where the next kept value goes, fast scans ahead looking for values to keep.

The problem shape

Given a sorted array, remove or deduplicate elements in place. The result is the new length (an integer); the first k cells of the array hold the kept elements. The constraint is O(1) extra space - no second array.

The key insight

fast walks the array from left to right. When it finds a value worth keeping (one that differs from the last value slow wrote), advance slow and copy it there. Everything at or before slow is the result so far; everything after is unexamined or discarded. Both pointers only move forward, so the whole sweep is O(n) time and O(1) space. The count of kept elements is slow + 1 - slow is an index, not a count, so the length is one more than the last write position.

Example: remove duplicates from a sorted array in place. Given [1, 1, 2, 2, 2, 3, 4], slow pins the last kept value and fast skips over the run of 2s, advancing slow only when it meets a value it has not kept - so three duplicates collapse into one write. The first four cells end up [1, 2, 3, 4] and the return is slow + 1 = 4. The walkthrough below traces exactly that input.

Solution walkthrough: Remove Duplicates

Walk [1, 1, 2, 2, 2, 3, 4]:

• slow=0 keeps 1. fast=1 sees 1 (same as last kept, skip). fast=2 sees 2 (different: advance slow to 1, write).
• fast=3,4 see 2 (skip). fast=5 sees 3 (advance slow to 2, write). fast=6 sees 4 (advance slow to 3, write).
• Return slow + 1 = 4. First 4 cells: [1, 2, 3, 4].

When to reach for two pointers

• The array is sorted and you need to find a pair or triplet satisfying a sum condition.
• You need to remove or deduplicate elements in-place without allocating extra space.
• The problem asks you to check if a string or array is a palindrome - compare from both ends converging inward.
• You need to partition an array in-place (Dutch flag, separate negatives and positives).
• A brute-force nested loop is O(n²) and the array is sorted - ask whether moving two pointers eliminates the inner loop.
• The problem involves area maximization or water trapping with height boundaries at two positions.