Sliding Window

Sliding window is the same-direction two-pointer shape (see Two Pointers) specialised to one recurring question: what is the best contiguous run of elements satisfying some condition? "Longest substring without repeating characters." "Smallest subarray with a sum at least k." "Longest substring with at most two distinct characters." All three are the same skeleton with the condition swapped out.

The skeleton

Two pointers, left and right, both starting at 0, bounding a window [left, right). right advances every iteration, adding one element to the window. After each addition, check the window's condition:

• If it's still valid (or you're looking for the longest valid window), record the answer and keep going.
• If it's become invalid (or you're looking for the shortest window satisfying a target), advance left — shrinking the window — until it's valid again.

int left = 0;
int best = 0; // or Integer.MAX_VALUE for a "smallest window" problem
Map<Character, Integer> counts = new HashMap<>();

for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    counts.merge(c, 1, Integer::sum);

    while (/* window at [left, right] is invalid */ counts.get(c) > 1) {
        char l = s.charAt(left);
        counts.merge(l, -1, Integer::sum);
        left++;
    }

    best = Math.max(best, right - left + 1);
}

Why the inner while doesn't make this O(n²)

That nested loop is the part people get nervous about — it looks like two loops, one inside the other. It isn't, because left never resets. Across the whole run of the algorithm, left moves from 0 to at most n, one step at a time, and it never moves backward. So the total number of times the inner loop body executes, summed across every iteration of the outer loop, is bounded by n — not n². This is the same amortised-cost argument that makes a stack-based algorithm like the largest-rectangle-in-a-histogram problem O(n) despite an inner while popping elements: count the total work across the whole run, not the worst case of one iteration.

Fixed-size vs. variable-size windows

Some problems fix the window size up front ("the maximum sum of any k consecutive elements") — there, right - left is always exactly k, and the loop is simpler: add the new right element, subtract the element leaving on the left, no inner while at all. That's exactly O(1) work on every single step, not just O(1) amortised across the whole run — a distinction that matters less for correctness than for how precisely you can explain the complexity when asked.

The harder, more common interview shape is a variable-size window, where the size itself is the answer or depends on the data — that's the skeleton above, and it's the one worth having cold.

What interviewers push on

• "What's the invariant?" — the property that's true of the window at the top of every loop iteration. If you can't state it precisely ("the window contains no character more than once"), you're pattern-matching the shape without understanding why it terminates correctly, and a slightly different condition in a follow-up question will produce a subtly wrong shrink condition.
• Off-by-one on the shrink. Shrinking one element too few or too many is the single most common bug — walk through why the while condition checks the state after adding the new element, not before.
• A follow-up that breaks the assumption. "What if the array has negative numbers?" kills a sliding-window solution to "smallest subarray with sum ≥ k" outright — the window's sum is no longer monotonic in its size, so shrinking on a sum threshold stops being valid, and a prefix-sum-plus-monotonic-deque approach is what the question is actually asking for. Noticing this rather than forcing the pattern to fit anyway is the signal.

Real-world use

This isn't just an interview trick — it's how a surprising amount of infrastructure actually works:

• TCP's sliding window is the literal namesake: a sender tracks a window of bytes sent but not yet acknowledged, and the window slides forward — the same left-edge-advances motion as the algorithm — as acknowledgements arrive. A separate, related mechanism (congestion control, not the sliding window itself) then grows or shrinks how large that window is allowed to be, based on whether packets are getting through — the "grow on success, shrink on a bad signal" shape people usually associate with the name.
• Rate limiters — a sliding time window (as opposed to a fixed one) tracking "how many requests has this key made in the last 60 seconds" is exactly this pattern applied to time instead of an array index.
• Streaming analytics and log monitoring — "average latency over the last 5 minutes," recomputed as new data arrives and old data ages out, without re-scanning the whole stream every time.
• Read-ahead / prefetching in a browser or a database's I/O layer keeps a moving window of "what's likely to be needed next" for the same reason: bound the work to what's actually changed since the last step.

Practice it

The judge measures actual CPU time, not your stated complexity — a solution that quietly rescans part of the window instead of sliding it still passes the samples and times out on the case sized to catch it.

Practice sliding-window problems