Two Pointers Pattern

Two Pointers Pattern

Many array problems have a brute-force solution that checks every pair with two nested loops, which is O(n²). The two pointers pattern keeps two indexes and moves them intelligently, so that each step rules out many pairs at once without checking them. The result is usually O(n) time and O(1) extra space.

It comes in two main shapes:

1. Opposite ends: one pointer at the start, one at the end, moving toward each other. Typical for sorted arrays, pair sums and palindromes.
2. Same direction: a slow and a fast pointer moving forward together. Typical for in-place rewriting (removing duplicates, partitioning) and for windows (see Sliding Window Pattern).

Opposite ends: Two Sum on a sorted array

int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        if (sum < target) left++;      // too small → the only way to grow is a bigger left value
        else right--;                  // too large → shrink with a smaller right value
    }
    return new int[0];
}

Why it's correct: if nums[left] + nums[right] is too small, then nums[left] paired with any element at or before right is also too small, because they're all ≤ nums[right]. So left can never be part of a solution and can be discarded. That single comparison eliminated a whole row of pairs. The same argument applies symmetrically to right. Each step discards one element, so the loop runs at most n times.

Without sorting, use a hash map instead (O(n) time, O(n) space). If the array isn't sorted and you sort it first, the total becomes O(n log n), and you lose the original indexes unless you sort (value, index) pairs.

3Sum: fix one, two-pointer the rest

Sort the array, fix the first element, and run two pointers on the rest for the complement. Skipping equal neighbours avoids duplicate triplets:

List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;      // same first element → same triplets
        if (nums[i] > 0) break;                              // smallest is positive → no zero sum possible
        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum < 0) left++;
            else if (sum > 0) right--;
            else {
                result.add(List.of(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;     // skip duplicates
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++; right--;
            }
        }
    }
    return result;
}

O(n²) time, down from O(n³). The duplicate-skipping lines are where most bugs happen, so trace an input like [-2, 0, 0, 2, 2] to check them. 4Sum adds one more fixed loop: O(n³).

Container With Most Water: move the limiting side

int maxArea(int[] h) {
    int left = 0, right = h.length - 1, best = 0;
    while (left < right) {
        best = Math.max(best, (right - left) * Math.min(h[left], h[right]));
        if (h[left] < h[right]) left++; else right--;       // move the shorter line
    }
    return best;
}

Why move the shorter line? The area is limited by the shorter side. Keeping it and moving the taller one can only shrink the width without raising the limit, so every such pair is worse. Discarding the shorter line loses nothing. This "which side can I safely discard?" argument is the reasoning behind every opposite-ends problem, and it's what interviewers want to hear.

Same direction: rewriting an array in place

The slow pointer marks where the next kept element goes. The fast pointer scans every element.

Remove duplicates from a sorted array (keep one of each):

int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int write = 1;                                     // nums[0] is always kept
    for (int read = 1; read < nums.length; read++) {
        if (nums[read] != nums[write - 1]) nums[write++] = nums[read];
    }
    return write;                                      // new length; the rest of the array is irrelevant
}

Move zeroes to the end, keeping the order of the other elements:

void moveZeroes(int[] nums) {
    int write = 0;
    for (int read = 0; read < nums.length; read++)
        if (nums[read] != 0) { int t = nums[write]; nums[write++] = nums[read]; nums[read] = t; }
}

Both are O(n) time and O(1) space. The read/write naming makes the invariant clear: everything before write is final.

Two arrays, two pointers: merging

Merging two sorted arrays walks one pointer through each. Merge Sorted Array (merge into the first array, which has extra space at the end) goes from the back, so nothing is overwritten before it's used:

void merge(int[] a, int m, int[] b, int n) {
    int i = m - 1, j = n - 1, write = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && a[i] > b[j]) a[write--] = a[i--];
        else a[write--] = b[j--];
    }
}

How to recognise the pattern

• The input is sorted, or sorting it doesn't break the problem, and you're looking for pairs or triplets meeting a condition.
• You're comparing elements from both ends (palindromes, reversal).
• You must modify an array in place with O(1) extra space.
• A brute force checks all pairs, and you can argue that some pairs can be discarded without checking.

Follow-up questions this topic invites — and their answers

Q: Why does two-pointer Two Sum require a sorted array? A: The decision to move left or right relies on the order. A sum that's too small means increasing it requires a larger left value, which is only guaranteed by moving right in a sorted array. On unsorted input, use a hash map of seen values instead.

Q: How do you avoid duplicate triplets in 3Sum without a set? A: Sort first, skip a fixed element equal to the previous one, and after recording a triplet, advance left and right past any repeated values. Each distinct triplet is then produced exactly once.

Q: Why move the shorter line in Container With Most Water? A: The container's height is capped by the shorter line. Any container keeping that line and moving the other inward has a smaller width and no greater height, so it can't be better. Discarding the shorter line is therefore safe.

Q: What's the complexity of 3Sum, and can it be better? A: O(n²) time after an O(n log n) sort, with O(1) extra space (ignoring output). O(n²) is widely believed to be essentially optimal for 3Sum in general, so interviews expect this solution.

Q: When should you use a hash map instead of two pointers? A: When the input can't be sorted, or sorting would lose information you need (original indexes), or when you process the data as a stream. Hash maps give O(n) time at the cost of O(n) space.