Two pointers and sliding window

Many array and string problems have a slow answer that tries every pair of positions, and a fast answer that walks through the data once with two positions. The two positions are usually called pointers, even though they are just indexes. Interviewers like these problems because the fast answer needs one clear reason ("this pointer can never be part of a better answer"), and explaining that reason shows how you think. The technique takes three shapes.

Shape 1: one pointer at each end

Use this when the data is sorted, or when the answer depends on the two ends of a range. Start left at the first position and right at the last. Look at the pair, decide which pointer can never be part of a better answer, and move only that one inward. Each step rules out one position for good, so the walk takes about n steps instead of n × n.

In "pair with a target sum" on a sorted list: if the sum is too big, the right value is too big even with the smallest value left, so move right back. If the sum is too small, move left forward. The picture shows the search for 9 in 1, 2, 4, 7, 11. (The costs O(n) and O(n²) are explained in Basics and maths.)

Container with the most water and trapping rain water use the same idea: move the shorter side, because the shorter side is what limits the answer.

Shape 2: a fixed-size window

For questions about every run of exactly k consecutive values (largest sum, average, count of something), keep a window of size k. When it slides one step right, add the value that enters and subtract the value that leaves. Recomputing each window from scratch costs k steps; sliding costs two.

Shape 3: a window that grows and shrinks

For "the longest (or shortest) run that follows a rule", move the right pointer forward one step at a time, and move the left pointer forward only when the window breaks the rule. Both pointers only ever move forward, so the total work is linear. The longest run without a repeated character is the classic example: remember where each character was last seen, and when the new character already appears inside the window, jump the left pointer just past that earlier position.

public class Main {
    // Opposite ends: positions of two values in a sorted array that add up to target.
    static int[] pairWithSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            long sum = (long) nums[left] + nums[right];
            if (sum == target) {
                return new int[] { left, right };
            }
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[] { -1, -1 };
    }

    // Window that grows and shrinks: longest run of characters with no repeats.
    static int longestUnique(String s) {
        int[] lastSeen = new int[128];
        java.util.Arrays.fill(lastSeen, -1);
        int start = 0;
        int best = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (lastSeen[c] >= start) {
                start = lastSeen[c] + 1;
            }
            lastSeen[c] = i;
            best = Math.max(best, i - start + 1);
        }
        return best;
    }

    public static void main(String[] args) {
        int[] pair = pairWithSum(new int[] { 1, 2, 4, 7, 11 }, 9);
        System.out.println(pair[0] + " " + pair[1]);
        System.out.println(longestUnique("abcabcbb"));
        System.out.println(longestUnique("abba"));
    }
}

1 3
3
2

def pair_with_sum(nums, target):
    """Opposite ends: positions of two values in a sorted list that add up to target."""
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return left, right
        if total < target:
            left += 1
        else:
            right -= 1
    return -1, -1


def longest_unique(s):
    """Window that grows and shrinks: longest run of characters with no repeats."""
    last_seen = {}
    start = best = 0
    for i, ch in enumerate(s):
        if last_seen.get(ch, -1) >= start:
            start = last_seen[ch] + 1
        last_seen[ch] = i
        best = max(best, i - start + 1)
    return best


i, j = pair_with_sum([1, 2, 4, 7, 11], 9)
print(i, j)
print(longest_unique("abcabcbb"))
print(longest_unique("abba"))

1 3
3
2

Notice the check lastSeen[c] >= start. Without it, "abba" goes wrong: when the second a arrives, its earlier position is already outside the window, and moving the left pointer back to it would make the window too long. A left pointer must never move backwards.

How to recognise these problems

• The input is sorted, or sorting it does not change the answer (pair sums, three sum, pairs with a small difference).
• The question is about consecutive values (values next to each other): "subarray" (a run of neighbouring values in a list), "substring" (a run of neighbouring characters), "window", "run".
• The obvious answer is two nested loops, and the inner loop repeats work the outer loop already did.

How to answer in an interview

Say the nested-loop answer and its O(n²) cost first. Then name the shape and give the reason a pointer may move: "the sum is too big, and the right value is too big even with the smallest partner, so it can go." Trace the first example, then give the cost: the pointers together move at most n steps, so the scan is O(n), or O(n log n) if you sorted first.

Common mistakes

• Overflow: two large 32-bit values can add up to more than a 32-bit integer holds. In Java, convert one value to long (a 64-bit type) before adding; Python integers do not overflow.
• Moving the wrong pointer, or moving one without a reason you can state.
• Off-by-one errors at the edges: test an empty input, a single value, and a window as long as the whole input.
• Starting a "best sum" at 0 when every value can be negative.
• Reporting the same group twice in three sum because repeated values were not skipped.

Recap

Two pointers replace a pair of nested loops when each step can rule out one position for good. Use opposite ends for sorted data, a fixed window for runs of length k, and a growing and shrinking window for "longest run that follows a rule".