Two pointers

Many array problems are secretly about pairs: two numbers that sum to a target, two ends of a palindrome, two walls that hold the most water. With n numbers in nums, checking every pair is O(n²). Two pointers gets it down to O(n). It keeps two indexes that only ever move forward (or inward). So together they make at most n moves.

The hard part isn’t the code, which is a short loop. It’s knowing why it is safe to move a pointer, because every move throws away possibilities for good. When you can say why the ones you threw away could never be the answer, the solution is correct. And you can say so in the interview.

What makes this hard

• Opposite ends: left starts at 0, right at the end, and they walk toward each other. Use it on sorted arrays and on anything symmetric, such as palindromes.
• Same direction: a read pointer visits everything and a write pointer marks where kept items go. Use it for in-place filtering, deduplication and partitioning.
• Fast and slow: one pointer moves two steps for every one the other moves. Use it to find cycles and midpoints in linked lists.
• Each move must rule something out for good. That argument is the proof that it’s correct.

How to spot it

• The input is sorted, and you need a pair or triple. Sorted order tells you which way to move. If the sum is too small, only the left pointer can make it bigger.
• “In place” or “O(1) extra space” on an array. Rearranging without a second array almost always means a read pointer and a write pointer.
• Comparing from both ends. Palindromes, reversing, squaring a sorted array with negatives.
• A linked list with a cycle or a middle. Fast and slow pointers, since you can’t index into a list.

It’s probably not two pointers when the input is unsorted and order matters, so you can’t sort it. Then a hash map is the usual answer.

Watch it run

Find two numbers in a sorted array that sum to 10. Watch the reason each step gives for dropping a number. When 1 + 11 is too big, 11 is the problem. 1 is the smallest number left, so 11 is too big with every partner, and can go. When 1 + 8 is too small, 1 is the problem. 8 is now the biggest number left.

nums (target 10)

1031426384115

leftright

1. left, right = 0, len(nums) - 1
2. while left < right:
3. pair_total = nums[left] + nums[right]
4. if pair_total == target: return [left, right]
5. if pair_total < target: left += 1 # need more
6. else: right -= 1 # need less

Sorted input. Start at both ends.

← BackStep →Play1 / 6

Every step drops one number that provably isn’t in any answer, so after at most n steps the pointers meet. That argument works only because the array is sorted. On an unsorted array the sum tells you nothing about which side to move.

The template

Opposite ends for pair sum, and same direction for removing duplicates in place:

JTwoPointers.javaPyexample.pyC#TwoPointers.csGomain.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.util.Arrays;

public class TwoPointers {
    static int[] pairSum(int[] nums, int target) {
        // Opposite ends. nums is sorted, so the sum tells us which pointer to move: too small
        // and only left can grow it, too big and only right can shrink it. Every move rules out one
        // number for good, so the loop runs at most once per number.
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int pairTotal = nums[left] + nums[right];
            if (pairTotal == target) return new int[] {left, right};
            if (pairTotal < target) left++;
            else right--;
        }
        return new int[0];
    }

    static int removeDuplicates(int[] nums) {
        // Same direction. read visits every element; write marks where the next kept value
        // goes. write never passes read, so we only overwrite values we've already looked at.
        int write = 0;
        for (int read = 0; read < nums.length; read++) {
            if (read == 0 || nums[read] != nums[read - 1]) nums[write++] = nums[read];
        }
        return write; // nums[0..write) holds each value once, in order
    }

    public static void main(String[] args) {
        check(Arrays.equals(pairSum(new int[] {1, 3, 4, 6, 8, 11}, 10), new int[] {2, 3}));
        check(pairSum(new int[] {1, 2}, 9).length == 0);
        int[] nums = {1, 1, 2, 3, 3, 3, 7};
        int keptCount = removeDuplicates(nums);
        check(Arrays.equals(Arrays.copyOf(nums, keptCount), new int[] {1, 2, 3, 7}));
        check(removeDuplicates(new int[0]) == 0);
        System.out.println("ok: pairSum and removeDuplicates");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError();
    }
}

In remove_duplicates, write is never ahead of read. So a write can only overwrite a value that read has already looked at. That’s the invariant to state for any read/write pointer solution. Everything before write is the answer so far. Everything from read on is unprocessed. And the gap between them is free space.

Variations

Three pointers for three sum

Sort, fix the first number with an outer loop, then run pair sum on the rest for the target minus that number. That’s O(n²), down from O(n³). Skip equal values for the fixed number and after each match, or you’ll report the same triple more than once.

Partitioning: sort colors

Three regions: 0s before low, 2s after high, unknown in between, with mid scanning the unknown part. A 0 swaps to low and both advance. A 2 swaps to high and only high moves, because the value swapped in hasn’t been looked at yet. This is the Dutch national flag algorithm, and it’s the partition step of quicksort with three regions instead of two.

Fast and slow pointers

Take a linked list with a cycle. A pointer that moves two steps at a time eventually laps one that moves one step, and they meet. Without a cycle, the fast one reaches the end. The same trick finds the middle of a list in one pass. When fast reaches the end, slow is halfway. It uses O(1) memory, where a set of visited nodes would use O(n).

Container with most water

The area between two walls is limited by the shorter one. Moving the taller wall inward can only shrink the width and can never raise the limit, so it can’t help. Always move the shorter wall. This is the same “rule out for good” argument, with height in place of sum.

Complexity

	Time	Extra memory
Pair sum on sorted input	O(n)	O(1)
Pair sum, sorting first	O(n log n)	O(1) to O(n), depends on the sort
Three sum	O(n²)	O(1) beyond the output
Remove duplicates, partitioning	O(n)	O(1)

Common mistake

Sorting when the problem asks for original indexes

Two sum on an unsorted array asks for the indexes of the pair. Sort it to use two pointers and the indexes are gone. Either sort (value, index) pairs, which costs O(n) memory anyway, or use a hash map, which is O(n) time instead of O(n log n). Two pointers is the right tool when the input arrives sorted, as in Two Sum II.

Say this out loud

The array is sorted, so if the sum is too small, the left number is too small even with the biggest partner. I can drop it and move left forward. Each step drops one number, so it’s O(n).

Interview questions

Interviewer asksWhy can you move left forward when the sum is too small? Couldn't nums[left] pair with something else?

Its biggest possible partner is nums[right], since everything beyond right was already ruled out, and even that sum is too small. Any other partner is smaller still. So nums[left] is in no answer and can be dropped. The same argument, mirrored, drops nums[right] when the sum is too big.

Interviewer asksThree sum returns duplicate triples. How do you fix it without a set?

Sort first. In the outer loop, skip a fixed number equal to the previous one. After finding a match, move both pointers and keep moving each while it equals the value it just left. Equal values are next to each other once sorted, so skipping them removes every duplicate in O(1) extra space.

Interviewer asksWhy does the fast pointer catch the slow one in a cycle? Can it jump over it?

Once both are in the cycle, the gap between them shrinks by exactly one each step. Fast gains two, and slow gains one. A gap that shrinks by one reaches zero. It can’t skip it. So they meet within one lap of the cycle, and the whole thing is O(n).

Practice

10 problems on LeetCode: 5 easy, 4 medium, 1 hard

1. Valid Palindrome↗(opens LeetCode in a new tab)

   Compare from both ends and walk inward, skipping what does not count.

   Easy
2. Move Zeroes↗(opens LeetCode in a new tab)

   A slow pointer marks where the next non-zero goes.

   Easy
3. Remove Duplicates from Sorted Array↗(opens LeetCode in a new tab)

   Read with one pointer, write with another that only moves on a new value.

   Easy
4. Squares of a Sorted Array↗(opens LeetCode in a new tab)

   The largest square is at one of the two ends.

   Easy
5. Linked List Cycle↗(opens LeetCode in a new tab)

   A fast pointer laps a slow one only if there is a loop.

   Easy
6. Two Sum II - Input Array Is Sorted↗(opens LeetCode in a new tab)

   Sorted order tells you which end to move when the sum is off.

   Medium
7. 3Sum↗(opens LeetCode in a new tab)

   Fix one number, then run sorted two-sum on the rest.

   Medium
8. Container With Most Water↗(opens LeetCode in a new tab)

   Moving the taller wall can never help, so always move the shorter one.

   Medium
9. Sort Colors↗(opens LeetCode in a new tab)

   Three pointers split the array into 0s, unknown and 2s.

   Medium
10. Trapping Rain Water↗(opens LeetCode in a new tab)

    The lower of the two running maxima decides the water at that end.

    Hard

Ticks are saved in this browser only. Clear your site data and they're gone.

Recap

• Use it when the input is sorted and you want pairs, when you must work in place, or when a linked list hides a cycle or a middle.
• Three shapes: opposite ends, read/write in the same direction, fast and slow.
• The proof: each move rules something out for good, and you can say why.
• Cost: O(n) time and O(1) memory, plus O(n log n) if you have to sort first.
• Watch for: problems that need original indexes (sorting loses them), and duplicate answers in three sum.