Two Pointers — Solve Array Problems in One Pass

The two pointers technique uses two indices that move through the data in a planned way. It often turns an O(n²) "check every pair" solution into a single O(n) pass with O(1) extra space.

There are two main styles:

1. Opposite ends — one pointer at the start, one at the end, moving towards each other. (Needs sorted data or a symmetric question.)
2. Same direction — a slow pointer that marks where to write and a fast pointer that reads. (Great for in-place array edits.)

Style 1: Opposite ends

Example — Valid Palindrome

Is "racecar" the same forwards and backwards? Compare the outermost characters and move inwards.

def is_palindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True

(The LeetCode version also skips non-alphanumeric characters and ignores case — add two small while loops to skip them.)

Example — Two Sum on a sorted array

Sorted input changes everything. Put l at the smallest number and r at the largest:

• sum too small → move l right (to a bigger number)
• sum too big → move r left (to a smaller number)
• equal → done

int[] twoSumSorted(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l < r) {
        int sum = nums[l] + nums[r];
        if (sum == target) return new int[]{l, r};
        if (sum < target) l++; else r--;
    }
    return new int[0];
}

Why it never misses the answer: when the sum is too small, nums[l] can't pair with anything left of r (those are even smaller), so discarding it is safe. Each step safely throws away one element → O(n), and no extra memory (unlike the hash map version).

Dry run — nums = [1, 3, 4, 6, 9], target = 10:

l	r	nums[l] + nums[r]	action
0	4	1 + 9 = 10	found (0, 4)

Try target = 7: 1+9=10 (too big, r--) → 1+6=7 ✓.

Example — 3Sum

Find all unique triplets that sum to 0. Sort, fix one number nums[i], then run the two-pointer search for −nums[i] on the rest. Skip equal neighbours to avoid duplicate triplets.

def three_sum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                      # same first number → same triplets
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0:
                l += 1
            elif s > 0:
                r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1                # skip duplicate second numbers
    return res

Sorting is O(n log n), the loops are O(n²) — far better than the O(n³) brute force.

Example — Container With Most Water

Pick two lines to hold the most water. Area = width × min(height). Start with the widest container; then move the shorter line inward, because moving the taller one can never help (width shrinks and the height is still capped by the shorter line).

def max_area(h):
    l, r, best = 0, len(h) - 1, 0
    while l < r:
        best = max(best, (r - l) * min(h[l], h[r]))
        if h[l] < h[r]:
            l += 1
        else:
            r -= 1
    return best

Style 2: Same direction (read / write pointers)

Example — Move Zeroes

Move all zeros to the end while keeping the order of the others, in place.

def move_zeroes(nums):
    write = 0                         # next position for a non-zero
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1

read scans everything; write only advances when it places a useful value. The same pattern solves Remove Duplicates from Sorted Array (write only when the value differs from the last written one).

Example — Merge Sorted Array (fill from the back)

When merging two sorted arrays into the first one's spare space, fill from the end so you never overwrite values you still need.

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

How to recognise a two-pointer problem

• The array is sorted (or you're allowed to sort it) and you need a pair/triplet with some sum.
• The question is about palindromes or reversing in place.
• You must modify the array in place with O(1) extra space.
• You're comparing elements from both ends.

Common mistakes

1. Using l <= r when the two pointers must point to different elements (use l < r).
2. Forgetting to skip duplicates in 3Sum — you return the same triplet many times.
3. Applying opposite-end pointers to an unsorted array — the "move left/right" logic only works when order is meaningful.
4. Moving both pointers when only one should move.

Key takeaways

• Two pointers replace nested loops: O(n) time, O(1) space.
• Opposite ends → sorted pairs, palindromes, containers. Same direction → in-place filtering.
• The proof idea: each move safely discards an element that can't be part of the answer.

Next up: the sliding window — two pointers that move in the same direction to track a range.