Two pointers and the sliding window

← Back to the section

We have covered arrays and learned to measure speed with big-O notation. Now take the most common technique that turns a slow solution into a fast one: two pointers. The idea is simple — instead of two nested loops, walk the data once while holding two movable marks inside it.

The technique does not fit every task, and the real skill is recognising when it does.

The problem: nested loops are expensive

Say a catalogue has sorted prices and you need two positions that add up to exactly the value of a gift card. The obvious solution is to try every pair:

for (int i = 0; i < prices.length; i++) {
    for (int j = i + 1; j < prices.length; j++) {
        if (prices[i] + prices[j] == target) return new int[]{i, j};
    }
}

That is O(N²). On a thousand positions it is about half a million pairs — still bearable. On a million positions it is half a trillion, which means hours. And the data is already sorted, yet we make no use of that.

Converging pointers

Put one mark at the start, the other at the end, and look at the sum:

• the sum is greater than the target — the only way to shrink it is to move the right mark left, toward smaller prices;
• the sum is smaller — move the left mark right;
• it matches — the answer is found.

Here is that walk in full, printing every pair it checks:

live example

public class TwoPointers {
    public static void main(String[] args) {
        int[] prices = {4, 9, 15, 22, 30, 41};
        int target = 37;
        int left = 0;
        int right = prices.length - 1;
        int steps = 0;
        while (left < right) {
            steps++;
            int sum = prices[left] + prices[right];
            System.out.println(prices[left] + " + " + prices[right] + " = " + sum);
            if (sum == target) break;
            if (sum < target) left++;
            else right--;
        }
        int pairs = prices.length * (prices.length - 1) / 2;
        System.out.println("steps: " + steps + ", pairs in a full scan: " + pairs);
    }
}

Every step moves one of the marks, and they move toward each other — so there are no more than N steps. That is O(N) instead of O(N²), with no extra memory.

Why this is sound: by moving the right mark left we throw away every pair made of that price and anything to the left of the current position — but all of them add up to even more, so none of them can fit. At each step only the certainly-useless part is discarded, and that is the whole essence of the technique.

Sorted order is mandatory. On unsorted data "the sum is too big, move the right mark" guarantees nothing: anything at all may sit on the left. With no order the technique does not apply — that is where a hash table helps instead.

Same-direction pointers

The second flavour: both marks travel the same way but at different speeds. The classic example is removing duplicates from a sorted array without allocating anything.

The slow mark holds the position to write to; the fast one reads straight ahead:

static int dedup(int[] codes) {
    if (codes.length == 0) return 0;
    int write = 0;
    for (int read = 1; read < codes.length; read++) {
        if (codes[read] != codes[write]) {
            write++;
            codes[write] = codes[read];
        }
    }
    return write + 1;
}

The same trick with different speeds also answers the cycle question for a linked list: the slow mark steps over one node, the fast one over two. If the list closes into a ring, the fast mark catches up sooner or later — the gap between them shrinks by one every iteration. If there is no ring, the fast mark simply runs into the end.

The fixed-width sliding window

A special case of same-direction pointers is keeping a segment of constant length between the marks. Say you need the largest sum of k consecutive days of revenue.

Naively — add up k numbers for every starting point: O(N·k). But neighbouring windows differ by just two days: one came in, one went out. So the sum does not have to be recomputed, only adjusted:

long sum = 0;
for (int i = 0; i < k; i++) sum += revenue[i];
long best = sum;
for (int i = k; i < revenue.length; i++) {
    sum += revenue[i] - revenue[i - k];
    best = Math.max(best, sum);
}

O(N) and no extra memory. The typical mistake is starting from best = 0: if all the revenue is negative, zero ends up as the "best" answer even though no such window exists.

The variable-width window

The most interesting flavour: the width is not given, the condition dictates it. For instance, find the longest stretch of a feed in which no category repeats.

The right edge always moves forward and widens the window. The left edge is pulled up only when the condition breaks — that is, when a repeat shows up. The window at every step is visible in the output:

live example

import java.util.HashMap;
import java.util.Map;

public class Window {
    public static void main(String[] args) {
        String feed = "abba";
        Map<Character, Integer> last = new HashMap<>();
        int left = 0;
        int best = 0;
        for (int right = 0; right < feed.length(); right++) {
            Integer seen = last.get(feed.charAt(right));
            if (seen != null && seen >= left) {
                left = seen + 1;
            }
            last.put(feed.charAt(right), right);
            best = Math.max(best, right - left + 1);
            System.out.println("window: " + feed.substring(left, right + 1));
        }
        System.out.println("longest stretch with no repeats: " + best);
    }
}

This hides the most common mistake of the technique: the left edge must never move backwards. The seen >= left check is exactly about that. On the string abba, when we reach the last a we find its earlier occurrence right at the start — but by then the window already begins later. Without the check the left edge would roll back to position 1, the window would become bba and the answer would grow to three, even though the repeat inside never went away.

Even though there is a nested while or a jump of the left edge inside, the time is still O(N): each edge crosses the array at most once, and the steps of both edges together never exceed 2N.

How to recognise the technique in a task

Signs that it is worth thinking about two pointers:

• the wording mentions a consecutive stretch, a "subarray", a "substring" — almost certainly a window;
• the data is sorted and you are after a pair or a triple with some property — converging pointers;
• elements have to be rearranged or filtered in place, with no extra memory — same-direction pointers;
• the naive solution is two nested loops, and moving to the neighbouring variant recomputes almost the same thing.

And the sign that it will not fit: the order of the elements does not matter, or the answer needs random access to data already passed — then you want a hash table or prefix sums.

How this is done in Java

The techniques in this article are written by hand: there is no ready-made "sliding window" in the standard library, and there cannot be — its shape depends on the task. What the pointers run over, though, has long been written and polished. And the choice of container decides whether the solution stays linear or quietly turns quadratic.

The reference array implementation in Java is ArrayList. Inside it is a plain array, swapped for a bigger one — roughly one and a half times longer — once the space runs out. So get(i) costs O(1), add at the end is amortised O(1) (the rare expensive move is spread over all the additions), while insertion and removal in the middle are O(N): the neighbours have to shift.

Pointers need exactly that O(1) access by index, so they run over an ArrayList at array speed. A LinkedList, however, is a trap for this technique: it is doubly linked, everything at the ends is O(1), but get(i) into the middle walks the references from an end, which is O(N). A "two pointers by index" loop on it quietly turns from O(N) into O(N²) while the code reads letter for letter the same. More about the class itself is in the article on linked lists.

The variable-width window also needs memory of what is currently inside. That is what a HashMap or a HashSet is for: access by key is O(1) on average, so the overall estimate of the pass is not spoiled. When the keys are characters or small numbers, people often use a plain counting array of 128 or 256 cells instead of a hash table — the same O(1), but without hashing and boxing.

The trap lives in same-direction pointers working "in place". The temptation to do the same thing on an ArrayList through remove(i) inside a loop ends badly twice over. First, every removal shifts the whole tail — that is O(N) per operation and O(N²) over the pass, exactly what we were escaping. Second, after a removal the next element takes the freed index while the loop counter has already moved on — so that element is never checked, and some duplicates stay in the list. The bug is silent: the list did get shorter and the result looks plausible. That is why the clean-up is done by overwriting: set(write, value) moves nothing, and the leftover tail is cut off with a single subList(write, size()).clear().

In short

• Two pointers means two movable marks instead of two nested loops; the usual win is O(N²) → O(N) with no extra memory.
• Converging marks move toward each other and only work on ordered data: each step discards a part that certainly cannot fit.
• Same-direction marks travel one way at different speeds: overwriting in place, finding a cycle in a list.
• The fixed-width sliding window adjusts the sum at the edges instead of recomputing it.
• The variable-width window is widened by the right edge and pulled up by the left one when the condition breaks; the left edge never moves backwards.
• The technique is recognised by the words "consecutive stretch" in the task and by the naive solution recomputing almost the same thing.

What to read next

• Prefix sums — what to do about a sum over a range when the window does not slide and the bounds are arbitrary.
• Hash tables — the fallback when the data is not sorted and converging marks do not work.
• Monotonic stack — the neighbouring one-pass technique: the nearest greater element without nested loops.
• Binary search on the answer — another way to kill a brute-force loop when the answer is monotonic.