Sliding Window: Turning O(n²) Subarray Scans Into One Clean Pass

You’re on a train, forehead almost on the glass, watching the countryside scroll by. The window is a fixed rectangle of the world — a barn here, three cows, a line of trees. A second later the train has rolled forward and the scene has shifted by exactly one: the barn slips off the left edge at the very instant a new tree appears on the right. Everything in between just stayed put and slid along.

Here’s the small, quiet question that turns out to be an entire algorithm. If I asked you how many cows are framed right now, and you already knew the answer a second ago — would you re-count every animal from scratch? Of course not. You’d take last second’s count, subtract the one that just slid off the left, add the one that just slid on at the right, and you’re done. One subtraction, one addition, no matter how wide the window is.

That instinct has a name. It’s the sliding window, and it’s the difference between an interview answer that runs in O(n²) and one that runs in O(n). By the end of this article you and I will have built both flavours of it — the fixed-width one and the stretchy one — and you’ll understand the single counting argument that confuses almost everyone about why it’s so fast.

Let’s start nowhere near a computer

Stay on that train a moment longer, because the window carries the whole idea.

The frame is a fixed width — call it k. As the train rolls, the view changes by a single step: one thing leaves the left, one thing enters the right, and the whole middle is untouched. So any question you can answer by summarising what’s in the frame — how many cows, the total weight of everything visible, the brightest object — gets cheap. You keep a running summary and nudge it each step: summary = summary − (what left) + (what entered). You never re-examine the middle. That’s a fixed window.

Now picture a different kind of window — a stretchy one. Imagine you’re packing a moving box and sliding a divider along a shelf of books, trying to grab the longest run of books where no two share the same colour. You push the right edge outward, greedily, taking one more book as long as the rule still holds. The moment you grab a book whose colour is already inside the box, the rule breaks — so you pull the left edge inward, dropping books off the back, until the duplicate colour is gone and the run is legal again. Then you go back to pushing right.

Two windows, one shared skeleton: a contiguous stretch, two edges, and a running summary of what’s inside. The fixed one moves as a rigid block. The variable one breathes. Everything else in this article is just those two pictures written down carefully.

Where you already meet this

Once you’ve seen “a contiguous stretch with a running summary,” it’s hiding all over your day:

• Your fitness tracker’s “steps in the last hour.” A window over time that slides forward every minute.
• A moving average on any stock chart or CPU graph — the mean of the last k readings, updated one tick at a time.
• The “best 10 seconds” of a video by loudness or motion — a fixed window swept across the timeline.
• Finding the shortest snippet of a document that contains all your search terms — a variable window that grows until it’s valid, then shrinks to get tight.

But the version that best shows how the idea generalises is rate limiting. When a service allows “100 requests per minute per user,” it’s holding a window over the timeline of your requests and asking, “how many fall inside the last 60 seconds?” The twist is that the elements don’t leave by position — they leave by timestamp. An entry drops out of the window not because a fixed number of newer ones arrived, but because the clock moved and it aged past the 60-second edge. The “what left” rule became a predicate on time instead of a fixed offset, yet the machinery is identical: a running count, an edge that advances, old entries expiring off the back. That single generalisation — the window boundary as a condition rather than a fixed width — is what powers the sliding-log rate limiter in designing a rate limiter. Same skeleton, a richer edge.

What it actually looks like

Let’s pin the picture down before we write a line of code. Here’s an array, a window three cells wide sitting over part of it, and the one number we carry alongside it — the running summary.

Look at the two labels L and R: the left and right boundaries of the window. Everything between them (inclusive) is “inside.” The whole game is moving L and R rightward across the array while keeping that summary — here a plain sum — correct and cheap. That’s why people call this the two-pointer technique: two indices, both marching in the same direction, never walking backward.

Let’s build one, step by step

We’ll start with the fixed window, watch the naive version waste time, fix it, and then graduate to the stretchy one.

Step 1 — the naive scan, and why it hurts

Say you want the largest sum of any k consecutive numbers. The obvious approach: consider every possible starting index, and for each one, add up its k elements.

Watch the two windows in that picture. The first sums cells 4 + 2 + 7. The second slides over by one and sums 2 + 7 + 1 — but 2 and 7 were just added a moment ago in the previous window. Every step throws away a fresh, correct partial sum and rebuilds an almost-identical one from scratch.

int best = Integer.MIN_VALUE;
for (int start = 0; start + k <= nums.length; start++) {
    int windowSum = 0;
    for (int i = start; i < start + k; i++) {  // re-add k elements every time
        windowSum += nums[i];
    }
    best = Math.max(best, windowSum);
}

The rule this breaks: don’t recompute what you already know. With n numbers and a window of size k, that inner loop runs k times for each of n positions — O(n · k) work, which becomes O(n²) when k grows with the input. An interviewer will nod politely and then ask for better.

Step 2 — the fixed window: subtract what left, add what entered

Here’s the fix, and it’s exactly the train-window instinct. When the window slides one step, only two cells change: one falls off the left, one arrives on the right. So don’t rebuild the sum — adjust it.

The old window summed to 13. Slide right: the 4 on the left leaves, the 1 on the right enters. The new sum is 13 − 4 + 1 = 10 — two arithmetic operations, regardless of how wide the window is.

int windowSum = 0;
for (int i = 0; i < k; i++) {          // build the very first window once
    windowSum += nums[i];
}
int best = windowSum;
for (int right = k; right < nums.length; right++) {
    windowSum += nums[right] - nums[right - k];  // one enters, one leaves
    best = Math.max(best, windowSum);
}

The rule: carry a running summary and repair it in O(1) on each slide. We build the first window the slow way once, then every later window costs a single add and a single subtract. The whole scan is now O(n) — each element is added exactly once when it enters and subtracted exactly once when it leaves.

Step 3 — fixed vs variable: is the width given, or discovered?

Everything so far assumed you know the window’s width up front — “sum of exactly k.” But a whole family of problems never hands you k. They hand you a rule, and the window’s size is part of the answer: the longest substring without repeats, the smallest subarray summing to at least T. The width isn’t an input; it’s what you’re solving for.

That’s the fork in the road:

• Fixed window — the width k is given. Both edges move together, in lockstep, one step per iteration. The window is a rigid ruler sliding along.
• Variable window — the width is discovered. The right edge charges forward greedily; the left edge only moves when a rule is violated. The window stretches and contracts as it goes.

The fixed case you’ve now built. The variable case is where the real depth lives, so let’s go there.

Step 4 — the variable window: grow right, shrink left while invalid

Take the classic: the longest substring with no repeated character. Given abcabcbb, the answer is 3 (the run abc). There’s no k to plug in — the window’s width is the thing we’re maximising.

The strategy is a rhythm. Push R right and pull the new character into the window. If that breaks the rule — the character’s already inside — pull L right, evicting characters off the back, until the window is legal again. After every step, the window is valid, so record its width if it’s the best so far.

Watch the collision in that picture. The window held abc; R advances onto the second a, but a is already inside — invalid. So L steps right, dropping the old a off the left, and now the window is bca, valid again, and we keep going.

Set<Character> window = new HashSet<>();
int left = 0;
int best = 0;
for (int right = 0; right < s.length(); right++) {
    char c = s.charAt(right);
    while (window.contains(c)) {        // rule broken? shrink from the left
        window.remove(s.charAt(left));
        left++;
    }
    window.add(c);
    best = Math.max(best, right - left + 1);
}

The summary here isn’t a sum — it’s a HashSet of the characters currently inside, so the “is the rule broken?” check is O(1). (If you’re fuzzy on why that lookup is constant-time, the hash tables article is the companion read.)

Now — the bug that separates a passing answer from a failing one. It’s tempting, when you hit a duplicate, to just start the window over from the character after the collision. That feels natural and it even gives correct answers. But it re-walks characters you’ve already visited, and on a string like aaaa… it degrades right back to O(n²). The fix is the discipline in the code above: L only ever moves forward, one eviction at a time, and never resets. That one constraint is the whole reason the next section’s complexity argument works — and it’s the thing interviewers are really probing.

Why the shrink loop is still O(n): the amortization argument

Here’s the part that trips up nearly everyone, and it’s worth slowing down for because it’s the single most important idea in this whole topic.

Look at that variable-window code again. There’s a for loop over right, and inside it a while loop that advances left. A loop inside a loop — surely that’s O(n²)? That’s the instinct, and it’s wrong, and understanding why it’s wrong is what separates someone who memorised the pattern from someone who owns it.

The key move is to stop counting per-iteration and start counting per-element. Forget the nesting for a second and ask a different question: over the entire run of the algorithm, how many times can left advance, total?

left starts at 0, only ever increases, and can never pass right, which tops out at n. So across the whole scan — summed over every iteration of the outer loop — left advances at most n times, total. Not n times per outer step. n times, full stop, shared across the entire pass. The inner while loop isn’t a fresh O(n) on each outer iteration; it’s all of them drawing down from one shared budget of n left-moves.

So tally the real work:

This way of counting — charging cost to elements rather than to loop iterations — is called amortized analysis, specifically the aggregate method. The honest picture in terms of the window itself: each element enters the window exactly once (when R sweeps past it) and leaves at most once (when L sweeps past it). Two touches per element, worst case. 2n operations. Any single iteration of the outer loop might do a big burst of shrinking — but that burst is “paying off” elements that will now never be touched again, so it can’t happen more than n times over the whole run.

There’s a deeper lesson hiding here that pays off far beyond this one pattern. A nested loop is not automatically O(n²). The quadratic only shows up when the inner loop can do O(n) work on every single outer iteration, independently. When the inner loop instead chips away at a bounded, shared resource — a pointer that only advances, a stack that each element enters once — the total is linear, and the nesting is a mirage. You’ll meet the exact same accounting again the moment you learn the monotonic-stack and monotonic-deque patterns.

Sliding window vs the brute-force scan

The window’s whole reason to exist is to replace a scan that re-examines overlapping work. Here’s the ledger, with n the input length, k the fixed width, and d the alphabet size for the string problem.

The fixed window trades nothing for its speed — same O(1) space as the brute force, just without the wasted re-adding. The variable window pays a small O(d) for the summary structure (the set or frequency map) and buys down the quadratic. Prefix sums are the cousin worth knowing: when you need range sums at arbitrary boundaries rather than one marching window, precompute once and answer each query in O(1).

The complete implementation

Both windows in one class — the fixed sum, the variable substring, and a bonus “jump” variant we’ll unpack in the interview corner:

package dev.fiveyear.window;
 
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
 
public final class SlidingWindow {
 
    private SlidingWindow() {}
 
    /** Largest sum of any k consecutive elements. O(n) time, O(1) space. */
    public static int maxSumOfK(int[] nums, int k) {
        if (k <= 0 || k > nums.length) {
            throw new IllegalArgumentException("k must be between 1 and nums.length");
        }
        int windowSum = 0;
        for (int i = 0; i < k; i++) {        // fill the first window
            windowSum += nums[i];
        }
        int best = windowSum;
        for (int right = k; right < nums.length; right++) {
            windowSum += nums[right] - nums[right - k]; // one enters, one leaves
            best = Math.max(best, windowSum);
        }
        return best;
    }
 
    /** Length of the longest substring with no repeated character. O(n) time. */
    public static int longestUniqueSubstring(String s) {
        Set<Character> window = new HashSet<>();
        int left = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            while (window.contains(c)) {      // shrink until the duplicate is gone
                window.remove(s.charAt(left));
                left++;
            }
            window.add(c);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
 
    /** Same answer, but the left edge JUMPS instead of stepping. O(n) time. */
    public static int longestUniqueJump(String s) {
        Map<Character, Integer> lastSeen = new HashMap<>();
        int left = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            Integer prev = lastSeen.get(c);
            if (prev != null && prev >= left) {
                left = prev + 1;              // leap past the old copy in one move
            }
            lastSeen.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

And here it is producing exactly the answers we traced by hand:

SlidingWindow.maxSumOfK(new int[] {2, 1, 5, 1, 3, 2}, 3);   // 9   → [5, 1, 3]
SlidingWindow.maxSumOfK(new int[] {4, 2, 7, 1, 3, 6}, 3);   // 13  → [4, 2, 7]
SlidingWindow.maxSumOfK(new int[] {-3, -1, -4, -2}, 2);     // -4  → [-3, -1]
 
SlidingWindow.longestUniqueSubstring("abcabcbb");           // 3   → "abc"
SlidingWindow.longestUniqueSubstring("bbbbb");              // 1   → "b"
SlidingWindow.longestUniqueSubstring("pwwkew");             // 3   → "wke"
SlidingWindow.longestUniqueSubstring("");                   // 0   → empty

Notice the negative-array case, -4. Because best is seeded with the first window’s real sum — not 0 — the algorithm handles all-negative input correctly. Seeding best = 0 instead is a subtle bug that only surfaces when every number is negative, which is exactly the edge case a test suite should carry.

The interview corner

Sliding window is one of the most-asked patterns precisely because the naive answer is easy and the good answer requires the one counting insight above. Walk in knowing the questions to ask and the ladder they’ll climb.

Ask these before you write a line:

• “Is the window a fixed size I’m given, or a size I have to find?” This is the whole fork — it decides whether L moves in lockstep with R or only on a broken rule. Say which one you’re building out loud.
• “What am I summarising, and can I update it in O(1)?” A sum and a count are trivial; “the max of the window” is not O(1) to maintain on eviction and needs a monotonic deque. If the summary can’t be repaired cheaply, sliding window may not be the tool.
• “Can the values be negative, or the array empty? What’s the valid range of k?” Negatives break any approach that assumes growing the window only helps; an empty input and k > n are the edge cases that throw or return early.

The follow-up ladder — where a strong candidate keeps climbing:

1. “Make the left edge jump instead of stepping.” Store each character’s last index in a map; on a duplicate, set left = lastIndex + 1 in one move instead of evicting one at a time. That’s the longestUniqueJump method above — same O(n), fewer operations, and it impresses.
2. “Smallest subarray with sum ≥ T.” Flip the objective: grow R until the sum reaches T, then shrink L as far as it’ll go while staying ≥ T, recording the minimum width. Same breathing motion, minimising instead of maximising.
3. “Longest substring with at most K distinct characters.” The summary becomes a HashMap of character → count; the window is invalid when the map has more than K keys, and shrinking decrements counts and removes keys that hit zero.
4. “Exactly K distinct” — how, when the window only knows ‘at most’?” The trick: exactly(K) = atMost(K) − atMost(K − 1). Sliding window naturally answers “at most,” so you run it twice and subtract. This reframing catches almost everyone off guard.
5. “Maximum of every window of size k.” Now the summary is a max, which a set can’t evict cheaply — reach for a monotonic deque that keeps candidates in decreasing order, giving O(n) overall. That’s the natural sequel, and it lives in queues and deques.

Three mistakes that fail the round:

• Calling the nested shrink loop O(n²). It isn’t, and saying so shows you don’t understand your own solution. left advances at most n times across the entire scan — total work is 2n. This is the thing they’re testing.
• Resetting the left pointer on a violation. Restarting the window after a duplicate re-walks visited characters and quietly reintroduces the quadratic. L marches forward and never resets — that invariant is the algorithm.
• Seeding the best answer with 0 or shrinking with if instead of while. A 0 seed breaks all-negative inputs; a single if fails when several evictions are needed to restore the rule (think abba). Both produce right answers on friendly inputs and wrong ones on the adversarial cases interviewers hand you on purpose.

Where to go from here

You now own the core: a contiguous window, two pointers that only move right, and a summary you repair in O(1) — fixed when the width is given, variable when you grow right and shrink left on a broken rule. Three natural next stops:

• The monotonic deque — the upgrade for when your summary is a max or min that a set can’t evict cheaply, unlocking “sliding window maximum” in O(n). Start from queues and deques.
• Prefix sums and difference arrays — the sibling technique for arbitrary range queries rather than one marching window; often the right tool when the window isn’t contiguous in time.
• The two-pointer family at large — same “two indices, never backward” accounting powers pair-sum on sorted arrays, merging, and partitioning. Sliding window is one dialect of a language worth learning whole.

Next time your fitness app tells you how many steps you took in the last hour, you’ll know it isn’t re-counting your whole day every minute. It’s sliding a window forward, dropping what aged off the back, adding what just happened — one subtract, one add, and on to the next tick.