How the Sliding Window Pattern Works (Java)

Sliding window took me longer to get than two pointers, and I think I know why: the pointers are the easy part. The hard part is deciding what lives inside the window and when the window is allowed to keep growing. Get those two things right and the code writes itself; get them fuzzy and you flail.

So this hub is organized around those two questions rather than around the pointers. I’ll cover the fixed-vs-variable split, the bookkeeping that actually does the work, and then the three NeetCode “Sliding Window” problems that live on this site.

A window that moves in one direction

A sliding window is a contiguous run of an array or string, marked by a left and a right index. Unlike the two pointers pattern — where the indices start apart and close in — here both indices travel the same way, left to right, and the run between them stretches or shrinks as you go. The quick test for which one you’re in: if the answer is a run whose size you’re tuning, it’s a window; if it’s a pair at the two ends, it’s two pointers.

There are two flavors, and naming which one you’re in is half the battle:

• Fixed window. The width k never changes. You slide it one step at a time: add the element entering on the right, drop the one leaving on the left. Think “maximum sum of any k consecutive numbers.”
• Variable window. The width breathes. right pushes the window open; left collapses it whenever some condition breaks. Almost every interesting interview problem — Longest Substring, Minimum Window — is this kind.

The fixed case is barely more than a running total. The variable case is where the pattern earns its reputation, so that’s where I’ll spend the words.

The real question: what do you keep in the window?

The pointers just mark the boundary. The state is what tells you whether the current window is valid, and choosing it well is the whole skill:

• A running sum — for “subarray adds up to at least X” (this grow/shrink assumes non-negative elements, so widening the window only raises the sum; negatives need prefix sums or a monotonic deque instead).
• A set of what’s inside — for “no repeats.”
• A hash map of counts — for “contains all of these characters.”

Whatever you pick, the rule is that sliding the window has to update that state in $O(1)$. Add one element on the right, remove one on the left, adjust the total or the count. If updating the state costs a re-scan of the window, you’ve lost the linear time that made this worth doing.

Step through the demo above — the window grows to the right, then shrinks from the left as soon as the running sum clears the target, recording the smallest valid run it passes through. (This shrink-while-valid logic relies on non-negative elements; the template below is the longest-window flavor, which shrinks on the opposite condition.)

The variable-window template

Once you know your state, nearly every variable-window solution is this shape:

int left = 0;
// windowState: a sum, a Set, or a count map

for (int right = 0; right < arr.length; right++) {
    // 1. the element at `right` enters the window
    add(arr[right]);

    // 2. while the window breaks the rule, shrink from the left
    while (!valid()) {
        remove(arr[left]);
        left++;
    }

    // 3. the window is valid here — record the answer
    best = update(best, right - left + 1);
}

Careful, though: the loop above solves longest-window problems — it shrinks while the window is invalid and records right after, once validity is restored. The shortest valid window inverts it. For Minimum Window Substring you let right reach a valid window, then shrink while it stays valid, recording the width on each step before it breaks. Same three moves, but the while predicate flips from !valid() to valid(), and where you record best moves inside the shrink loop. That inversion — not just “where you write best” — is the part worth internalizing.

Three problems, easy to nasty

Best Time to Buy and Sell Stock

The gentlest entry. Walk the prices once, remember the lowest you’ve seen, and at each day check the profit against that low. You can read it as a window whose left edge only ever jumps to a new minimum — no shrinking loop at all. It’s really a one-pass scan, which is why I also file it under greedy one-pass thinking; the full walkthrough is in Best Time to Buy and Sell Stock.

Longest Substring Without Repeating Characters

Here the window breathes for real. Grow right across the string; the moment the incoming character is already inside, shrink left until it isn’t, then record the length. The state is “the characters currently in the window,” and the only subtlety is how you store it — a Set that you step, or an int[128] of last-seen positions that lets left leap instead of crawl. That optimization is the interesting part, and it’s in Longest Substring Without Repeating Characters.

Minimum Window Substring

The hardest of the three, and the reason the “shortest valid” reading matters. You keep a count map of the characters you still need, expand right until the window covers all of them, then shrink left as far as you can while it stays covered — recording the smallest width each time it’s valid. The bookkeeping (a need map plus a have counter so validity is an $O(1)$ check, not a map comparison) is what keeps it linear. I break the whole thing down in Minimum Window Substring.

The other three on NeetCode’s list — Longest Repeating Character Replacement, Permutation in String, and Sliding Window Maximum — are variations on the same two questions. The last one adds a monotonic deque to answer “max of the current window” in amortized $O(1)$, and I’ll give it room when I write it up.

Why it’s linear

right visits each element exactly once, and left only ever chases it forward — it never rewinds — so between them they take at most $2n$ steps. That’s $O(n)$ time no matter how much the window breathes in between. The memory is just whatever you’re holding in the window: a number or two is $O(1)$; a set or count map over an alphabet of size k is $O(k)$, which stays effectively constant for ASCII and grows only for arbitrary Unicode.

The mistake I kept making

Early on I’d shrink the window with an if instead of a while, which quietly works until the day two elements need to leave at once. If you take one habit from this: the shrink step is a loop, not a single step. Which way it drives — shrinking until the window becomes valid (the longest-window problems) or while it stays valid (the shortest ones, like Minimum Window) — flips with the question, but it’s always a loop, and you always keep the best window you saw.

Outside interviews it’s the shape of a sliding-window rate limiter — the requests inside your time window are the state, they age out on the left as time moves right, and you accept or reject based on whether the window is still under the limit. Same three moves. Spotting that overlap is what made the interview version click for me, coming from a backend background.

References

• NeetCode 150 — Sliding Window — where the problem set comes from.