Two Pointers: Solve Problems by Coordinating Indices

Imagine two friends searching a long corridor of numbered rooms for a pair of rooms whose numbers add up to a target. One starts at the front and the other at the back. Whenever the total is too low, the person at the front steps forward to a bigger room number. When it is too high, the person at the back steps in to a smaller one. They meet in the middle having checked very few pairs, and they never needed to try every combination.

That picture is the two pointers technique. You use two indices instead of one, and you move them cleverly so that a problem that looks like it needs a loop inside a loop is solved in a single pass. It is one of the most useful patterns in interviews, and you have already seen it twice: reversing an array, and checking a palindrome from both ends.

• The two main shapes of the technique: pointers from opposite ends, and pointers in the same direction.
• How to explain why a pointer move is safe, which is what interviewers really ask.
• How to solve pair sum, container with most water, 3Sum, deduplication and trapping rain water.
• How to tell when two pointers do not apply.

Keep two indices, and at every step move one of them in a way that provably discards at least one candidate without losing any answer. If every step shrinks the search space by one candidate, the whole process takes O(n) steps, not O(n^2).

Start with left = 0 and right = n - 1. Compare something about a[left] and a[right], and move one pointer inwards. Stop when they meet. This usually needs sorted data, or a property that makes the choice of which pointer to move clear.

Problem. Given a sorted array and a target, find two different positions whose values add up to the target.

Brute force. Try every pair: O(n^2).

Two pointers. Look at sum = a[left] + a[right]:

• if sum == target, we found the pair;
• if sum < target, we need a bigger sum, so move left right (towards bigger values);
• if sum > target, we need a smaller sum, so move right left.

Why is the move safe? Suppose sum < target. Every other candidate partner for a[left] lies in a[left + 1 .. right - 1], and those values are all <= a[right] because the array is sorted. So a[left] + a[j] <= a[left] + a[right] < target for every j: a[left] cannot pair with anything left in the window. We lose nothing by discarding it. The case sum > target is the mirror image: a[right] is too big to pair with anything, so discard it.

This argument is the invariant of the algorithm: if any valid pair exists, it lies inside a[left..right]. It is true at the start, and each step preserves it. When the pointers meet (left == right), the window holds a single element, no valid pair remains, and we report "not found".

We use left < right (not <=) because the two positions must be different.

Problem. The array height describes vertical lines at positions 0, 1, ..., n - 1. Choose two lines that, with the x-axis, hold the most water. The water level is limited by the shorter line, so the area for lines at left and right is min(height[left], height[right]) × (right - left).

Brute force. Try every pair: O(n^2).

Two pointers. Start with the widest container (left = 0, right = n - 1), record the area, and then move the pointer at the shorter line inwards.

Why the shorter one? Suppose height[left] < height[right]. Any container that keeps left and uses a smaller right' has a smaller width, and its height is still at most height[left] (the shorter line limits it). So it cannot beat the area we just computed, and left can never be part of a better container. We can discard left. Moving the taller line would be pointless, since the container's height cannot go above the shorter line while the width gets smaller.

Problem. Given an array of integers, find all unique triplets (a, b, c) with a + b + c = 0.

Brute force. Three nested loops: O(n^3).

Better. Sort the array. Fix the first number a[i]. Then you need two numbers in the rest of the array (positions after i) that sum to -a[i]. That is pair sum on a sorted range, solved with two pointers in O(n). Total: O(n^2).

To keep triplets unique, skip repeated values: skip i if a[i] == a[i - 1], and after finding a triplet, move both pointers past duplicate values. If a[i] > 0, no triplet starting at i can sum to zero (all later values are at least as large), so we can stop.

// File: Main.javaimport java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Main {    // Sorted input. Returns {left, right} or an empty array.    static int[] pairSumSorted(int[] a, int target) {        int left = 0;        int right = a.length - 1;        while (left < right) {            long sum = (long) a[left] + a[right];     // long: the sum of two ints can overflow int            if (sum == target) {                return new int[] {left, right};            }            if (sum < target) {                left++;            } else {                right--;            }        }        return new int[0];    }    static long maxWater(int[] height) {        int left = 0;        int right = height.length - 1;        long best = 0;        while (left < right) {            long area = (long) Math.min(height[left], height[right]) * (right - left);            best = Math.max(best, area);            if (height[left] < height[right]) {                left++;                               // the shorter line limits every container using it            } else {                right--;            }        }        return best;    }    static List<List<Integer>> threeSum(int[] nums) {        int[] a = nums.clone();        Arrays.sort(a);        List<List<Integer>> result = new ArrayList<>();        for (int i = 0; i < a.length - 2; i++) {            if (a[i] > 0) {                break;                                // the smallest is positive: no zero sum possible            }            if (i > 0 && a[i] == a[i - 1]) {                continue;                             // skip a repeated first value            }            int left = i + 1;            int right = a.length - 1;            while (left < right) {                long sum = (long) a[i] + a[left] + a[right];                if (sum == 0) {                    result.add(Arrays.asList(a[i], a[left], a[right]));                    left++;                    right--;                    while (left < right && a[left] == a[left - 1]) {                        left++;                       // skip repeated second values                    }                    while (left < right && a[right] == a[right + 1]) {                        right--;                      // skip repeated third values                    }                } else if (sum < 0) {                    left++;                } else {                    right--;                }            }        }        return result;    }    static String show(List<List<Integer>> triplets) {        StringBuilder sb = new StringBuilder();        for (List<Integer> t : triplets) {            sb.append('(').append(t.get(0)).append(',').append(t.get(1)).append(',').append(t.get(2)).append(") ");        }        return triplets.size() + " triplets: " + sb.toString().trim();    }    public static void main(String[] args) {        System.out.println(Arrays.toString(pairSumSorted(new int[] {1, 2, 4, 7, 11, 15}, 15)));        System.out.println(Arrays.toString(pairSumSorted(new int[] {2, 5}, 4)));        System.out.println(Arrays.toString(pairSumSorted(new int[] {-3, -1, 0, 2, 5}, 2)));        System.out.println(Arrays.toString(pairSumSorted(new int[] {1, 1}, 2)));        System.out.println(Arrays.toString(pairSumSorted(new int[] {}, 3)));        System.out.println(maxWater(new int[] {1, 8, 6, 2, 5, 4, 8, 3, 7}) + " " + maxWater(new int[] {1, 1}) + " " + maxWater(new int[] {4, 3, 2, 1, 4}) + " " + maxWater(new int[] {5}));        System.out.println(show(threeSum(new int[] {-1, 0, 1, 2, -1, -4})));        System.out.println(show(threeSum(new int[] {0, 0, 0, 0})));        System.out.println(show(threeSum(new int[] {1, 2, 3})));    }}

[2, 4][][0, 4][0, 1][]49 1 16 02 triplets: (-1,-1,2) (-1,0,1)1 triplets: (0,0,0)0 triplets:

Dry run of pairSumSorted([1, 2, 4, 7, 11, 15], 15):

Four steps for six elements instead of up to 15 pairs.

Dry run of maxWater([1, 8, 6, 2, 5, 4, 8, 3, 7]):

The best area is 49, found at the second step, and the remaining steps could not beat it.

Dry run of threeSum on [-1, 0, 1, 2, -1, -4]: sorted it is [-4, -1, -1, 0, 1, 2].

Complexity: pair sum and container are O(n) time and O(1) extra space. 3Sum is O(n^2) (sorting is O(n log n), and then n iterations each with an O(n) two-pointer pass), with O(1) or O(log n) extra space for the sort, not counting the output.

Here both pointers start at the left and move right, at different speeds or for different roles.

• The reader scans every element.
• The writer marks where the next kept element should be placed.

Everything to the left of the writer is the finished output. This pattern does in-place filtering with O(1) extra space.

Problem. Remove duplicates in place from a sorted array, so each value appears once. Return the number of unique values k; the first k elements of the array must hold them in order. What is beyond position k does not matter.

Because the array is sorted, duplicates sit together. The writer position write is where the next new value goes. The reader looks at each element: if it differs from the last value we kept (a[write - 1]), it is new, so copy it to a[write] and advance the writer.

// File: Main.javaimport java.util.Arrays;public class Main {    // Returns the number of distinct values; the first that many positions hold them.    static int removeDuplicates(int[] a) {        if (a.length == 0) {            return 0;        }        int write = 1;                               // a[0] is always kept        for (int read = 1; read < a.length; read++) {            if (a[read] != a[write - 1]) {           // differs from the last kept value                a[write] = a[read];                write++;            }        }        return write;    }    public static void main(String[] args) {        int[] a = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};        int k = removeDuplicates(a);        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(a, k)));        int[] single = {7};        System.out.println(removeDuplicates(single) + " " + removeDuplicates(new int[] {}) + " " + removeDuplicates(new int[] {2, 2, 2}));    }}

5 [0, 1, 2, 3, 4]1 0 1

Dry run on [0, 0, 1, 1, 1, 2]:

The answer is 3, and the first three positions hold 0, 1, 2. The reader scans n elements and the writer never moves faster than the reader, so the time is O(n) and the space O(1). Moving zeroes to the end, from the arrays article, is the same pattern with a different "keep" rule.

When you have two sorted sequences, use one pointer in each. You did exactly this when merging two sorted arrays, and when merging two sorted linked lists. The same idea gives the intersection of two sorted arrays, and the "is s a subsequence of t" check (advance the pointer in s only when the characters match).

In Linked Lists, the slow pointer moved one step and the fast pointer two steps. That is the same-direction pattern with different speeds, used for finding the middle and detecting cycles.

• Unsorted data where original positions matter. If you need the indexes in the original array and the array is unsorted, sorting loses them. A HashMap (see Hashing) is usually the right tool.
• No monotonic property. The pointer moves must be justified by "this candidate can never be part of an answer". If you cannot argue that, the technique is not valid for the problem.
• Subarray problems with negative numbers. Pointer logic for sums assumes that adding elements always increases the total. With negatives, that fails. We study this in Sliding Window and Prefix Sums.

• Using left <= right when the two positions must differ. A value could pair with itself.
• Moving the wrong pointer. Always justify the move with "this element can never be part of an answer".
• Forgetting that sorted is required for the pair-sum pointer logic.
• Duplicates in 3Sum. Skip repeated values for the first element and after each found triplet, or you will report the same triplet more than once.
• Overflow. Sums of two or three ints can overflow. Use long for the sum.
• Empty and one-element arrays. Loops like i < a.length - 2 handle short arrays safely, but check.
• Reading past the end when you compare a[i] with a[i + 1] or a[right + 1]. Check the bounds first.
• Forgetting to return the new length in in-place filtering, or assuming the elements beyond it are meaningful.
• Applying the pattern to unsorted data without sorting, or sorting when the indexes were needed.

static boolean hasPairBuggy(int[] a, int target) {    int left = 0;    int right = a.length - 1;    while (left <= right) {        int sum = a[left] + a[right];        if (sum == target) {            return true;        }        if (sum < target) {            right--;        } else {            left++;        }    }    return false;}

// File: Main.javaimport java.util.Arrays;public class Main {    static long[] sortedSquares(int[] a) {        long[] result = new long[a.length];        int left = 0;        int right = a.length - 1;        for (int pos = a.length - 1; pos >= 0; pos--) {            long leftSquare = (long) a[left] * a[left];            long rightSquare = (long) a[right] * a[right];            if (leftSquare > rightSquare) {                result[pos] = leftSquare;                left++;            } else {                result[pos] = rightSquare;                right--;            }        }        return result;    }    public static void main(String[] args) {        System.out.println(Arrays.toString(sortedSquares(new int[] {-4, -1, 0, 3, 10})));        System.out.println(Arrays.toString(sortedSquares(new int[] {-7, -3, 2, 3, 11})));        System.out.println(Arrays.toString(sortedSquares(new int[] {-100000, 5})));        System.out.println(Arrays.toString(sortedSquares(new int[] {})));    }}

[0, 1, 9, 16, 100][4, 9, 9, 49, 121][25, 10000000000][]

// File: Main.javaimport java.util.Arrays;public class Main {    static int removeDuplicatesAtMostTwice(int[] a) {        int write = 0;        for (int read = 0; read < a.length; read++) {            if (write < 2 || a[read] != a[write - 2]) {                a[write] = a[read];                write++;            }        }        return write;    }    public static void main(String[] args) {        int[] a = {1, 1, 1, 2, 2, 3};        int k = removeDuplicatesAtMostTwice(a);        System.out.println(k + " " + Arrays.toString(Arrays.copyOf(a, k)));        int[] b = {0, 0, 1, 1, 1, 1, 2, 3, 3};        int m = removeDuplicatesAtMostTwice(b);        System.out.println(m + " " + Arrays.toString(Arrays.copyOf(b, m)));        System.out.println(removeDuplicatesAtMostTwice(new int[] {}) + " " + removeDuplicatesAtMostTwice(new int[] {5, 5, 5, 5}));    }}

5 [1, 1, 2, 2, 3]7 [0, 0, 1, 1, 2, 3, 3]0 2

// File: Main.javapublic class Main {    static boolean hasPairBuggy(int[] a, int target) {        int left = 0;        int right = a.length - 1;        while (left <= right) {            int sum = a[left] + a[right];            if (sum == target) {                return true;            }            if (sum < target) {                right--;            } else {                left++;            }        }        return false;    }    // Moves fixed, but still using <= to show the second bug on its own.    static boolean hasPairSelfUse(int[] a, int target) {        int left = 0;        int right = a.length - 1;        while (left <= right) {            int sum = a[left] + a[right];            if (sum == target) {                return true;            }            if (sum < target) {                left++;            } else {                right--;            }        }        return false;    }    static boolean hasPairFixed(int[] a, int target) {        int left = 0;        int right = a.length - 1;        while (left < right) {            long sum = (long) a[left] + a[right];            if (sum == target) {                return true;            }            if (sum < target) {                left++;            } else {                right--;            }        }        return false;    }    public static void main(String[] args) {        int[] a = {1, 2, 4, 7, 11, 15};        System.out.println(hasPairBuggy(a, 15) + " " + hasPairFixed(a, 15));        int[] b = {2, 5};        System.out.println(hasPairSelfUse(b, 4) + " " + hasPairFixed(b, 4));    }}

false truetrue false

// File: Main.javapublic class Main {    static int trap(int[] height) {        int left = 0;        int right = height.length - 1;        int leftMax = 0;        int rightMax = 0;        int water = 0;        while (left < right) {            if (height[left] < height[right]) {                if (height[left] >= leftMax) {                    leftMax = height[left];            // a new tallest wall on the left: no water here                } else {                    water += leftMax - height[left];                }                left++;            } else {                if (height[right] >= rightMax) {                    rightMax = height[right];                } else {                    water += rightMax - height[right];                }                right--;            }        }        return water;    }    public static void main(String[] args) {        System.out.println(trap(new int[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1}));        System.out.println(trap(new int[] {4, 2, 0, 3, 2, 5}));        System.out.println(trap(new int[] {}));        System.out.println(trap(new int[] {3}));        System.out.println(trap(new int[] {1, 2, 3}));    }}

69000

• Next: Sliding Window: Efficient Subarray and Substring Problems is the same-direction pattern applied to contiguous ranges, where two pointers mark the two ends of a window.
• Related: Searching and Sorting explains the sorting step that many two-pointer solutions begin with, and Hashing is the alternative for unsorted pair-sum problems.
• Practice habit: each time you move a pointer, say out loud, "I am discarding this element because ...". If you cannot finish the sentence, the move is a guess.