Two Pointers

On this page

The Idea
Build It
Know It
Break It
Use It

Quick reference

Opposite-direction sweep	O(n)
Same-direction (slow/fast) sweep	O(n)
Brute-force pair check (for comparison)	O(n²)

The Idea

Imagine two fingers on the same array. Each finger can move without the other finger. The brute-force method checks each pair of elements with a nested loop. For each element, it looks at each other element again. This is O(n²) work. Two pointers is a better method. For many problems, you do not need each pair. You need the pairs to meet in a good order. Then each finger moves across the array one time only.

You can place the fingers in two common ways. In the first way, the fingers start at opposite ends. The fingers move toward each other and meet in the middle. In the second way, the fingers start together at the front. One finger moves ahead of the other finger. Both fingers move in the same direction. The correct way depends on the question. But both ways replace an O(n²) nested scan with one O(n) sweep.

The main benefit is a change from O(n²) to O(n). The O(n²) method checks each pair. The O(n) method moves each pointer across the array one time. This method uses O(1) extra space. It does not need an extra array or a lookup structure. It needs only two index variables.

Build It

Two pointer shapes

// Opposite direction: start at both ends and move inward.
left = 0
right = length - 1
while left < right:
    ... look at arr[left] and arr[right] ...
    move left forward, or right backward, or both. The result decides the move.

// Same direction: both pointers start at the front. One pointer is the slow writer.
// The other pointer is the fast scanner. The fast scanner moves ahead of the slow writer.
slow = 0
for fast from 0 to length - 1:
    ... decide if arr[fast] belongs at position slow ...
    if it does: put it there. Then slow += 1

opposite-direction — converge from both ends

function hasPairWithSum(sortedArr, target):
    left = 0
    right = length(sortedArr) - 1
    while left < right:
        sum = sortedArr[left] + sortedArr[right]
        if sum == target:
            return true
        elif sum < target:
            left += 1        // The sum is too small. A larger left value is the only way to increase it.
        else:
            right -= 1        // The sum is too large. A smaller right value is the only way to decrease it.
    return false

Each step removes a full row or column of the pair grid, not only one pair. This changes O(n²) pair-checking into O(n).

same-direction — slow/fast in-place filter

function moveMatchingToFront(arr, matches):
    slow = 0
    for fast from 0 to length(arr) - 1:
        if matches(arr[fast]):
            swap(arr[slow], arr[fast])
            slow += 1
    return slow    // Each element before this index matches. Each element after it does not match.

The fast pointer explores. The slow pointer marks the last good position. (The Linked Lists topic in Phase 2 uses this same slow and fast method. It moves .next pointers through a chain, not indices through an array. The idea is the same.)

Know It

Both pointer shapes change the growth curve in the same way. They replace a nested O(n²) scan with one pass. Each pointer moves a maximum of n steps. The method uses only two index variables.

Operation	Time	Space	Why
Opposite-direction sweep	O(n)	O(1)	The left pointer and the right pointer together cover a maximum of n steps before they cross. The method never visits an element two times.
Same-direction (slow/fast) sweep	O(n)	O(1)	The fast pointer visits each element one time. The slow pointer moves only forward. The slow pointer never goes past the fast pointer. The total work is linear in n.
Brute-force pair check (for comparison)	O(n²)	O(1)	A check of each (i, j) pair with a nested loop is the cost. Two pointers exists to prevent this cost.

Break It

The pointers cross because there is no stop condition

the loop condition does not check left < right (or fast < length)

If you forget the crossing check, two problems can occur. The left and right pointers can move past each other. Or the fast pointer can move past the end of the array. The first problem makes an infinite loop. The second problem makes an out-of-bounds read. The loop condition is not optional. The loop condition makes sure that the loop stops.

The skip-duplicates step is broken but gives no error

the array has repeated values and a duplicate-skipping step is missing or wrong

Problems such as 3Sum must skip repeated values after a match. If they do not, the program reports the same triplet more than one time. Write the skip step correctly. A skip such as "skip while arr[i] == arr[i-1]" is correct. A skip such as "skip while arr[i] == arr[i+1]", or a skip on the wrong pointer, is a problem. It skips too much and misses correct answers. Or it skips too little and reports duplicates.

You assume sorted input that the pattern needs

you use the opposite-direction sweep on unsorted data

The opposite-direction pattern works for one reason. When you move the left pointer forward, the sum increases. When you move the right pointer backward, the sum decreases. This is true only for sorted data. If you run the pattern on an unsorted array, it does not crash. But it gives wrong answers with no error. The rule "the sum is too small, so move left" is no longer correct.

Use It

Two Sum II - Input Array Is Sorted

The input is sorted. The two numbers that you want are between the two ends. Start one finger at each end. If the sum is too large, move the right finger inward. If the sum is too small, move the left finger inward.

Easy

3Sum

Sort the array. Then fix one number at a time. Solve the remaining two-number problem on the rest of the array. Use the opposite-direction sweep from Two Sum II. Skip repeated values so the program does not report the same triplet two times.

Medium

Container With Most Water

Start with the widest container. Put the pointers at both ends. Move the pointers inward. Always move the pointer at the shorter wall. The taller wall was never the limit for a wider container. So you keep the taller wall.

Medium

Sort Colors

Use three pointers, not two. One pointer marks the next place for a low value. One pointer marks the next place for a high value. One current scanner moves between them. The scanner swaps the current element into position as it moves.

Medium

Remove Duplicates from Sorted Array

One pointer scans ahead and reads each element. A second, slower pointer marks the last unique place. The slow pointer moves only when the scanner finds a new value.

Easy

Squares of a Sorted Array

The name helps here. Put two pointers at both ends of the sorted array. The largest square comes from the end with the larger absolute value. Fill the answer array from the back to the front.

Easy

Move Zeroes

Use the same-direction two-pointer sweep from Build It. A slow pointer marks the place for the next non-zero value. A fast pointer scans ahead. The pointers swap when the fast pointer finds a non-zero value.

Easy

Backspace String Compare

Walk both strings from the end to the front with two separate pointers. Skip a character each time you see a '#'. A comparison from the back manages the backspaces. You do not build a new string.

Easy

Reverse Vowels of a String

Use the same opposite-direction sweep as Valid Palindrome. But stop and swap only when both pointers are on vowels. Each consonant moves past with no change.

Easy

Valid Palindrome

Use the same opposite-direction two-pointer sweep from Arrays & Strings Fundamentals. Here it has its real name. Move toward the middle from both ends. Skip characters that are not letters or numbers. Compare with no attention to case.

Easy