Sliding Window

An interviewer asks: “Given an array of daily transaction counts, find the highest total over any 7 consecutive days.” The brute-force candidate writes two nested loops and re-adds the same numbers thousands of times. You’re going to see why that re-adding is the entire problem — and how deleting it turns O(n·k) into O(n) with three lines of arithmetic.

The Goal

By the end of this module you can:

• Recognize a sliding window problem from the wording in under 30 seconds — the word “contiguous” is the flare
• Explain the core trick: subtract what leaves the window, add what enters, never re-scan the middle
• Implement the fixed-size window template in Java from memory (max sum of k elements)
• Implement the variable-size window template — grow right until invalid, shrink left until valid
• Solve “Longest Substring Without Repeating Characters” using the HashSet from Arrays & Hashing
• Spot when sliding window does NOT apply, so you don’t force it onto DP problems

The Lesson

The core insight — stop recomputing the chunk

Take “max sum of any 3 consecutive elements” on [4, 2, 9, 7, 1, 5].

Brute force: for every starting index, loop over the next 3 elements and add them up. That’s two loops — O(n·k). But look at what you’re actually computing:

window 1:  4 + 2 + 9        = 15
window 2:      2 + 9 + 7    = 18
window 3:          9 + 7 + 1 = 17

Window 2 shares 2 + 9 with window 1. You already know 2 + 9 — you computed it one step ago. The only difference between consecutive windows is one element fell off the left, one came in on the right. So:

window 2 = window 1 - 4 (left) + 7 (right)  →  15 - 4 + 7 = 18

That’s the whole pattern. The answer for each window is the previous answer, patched in O(1). One pass, O(n), no matter how big k gets.

For n = 1,000,000 and k = 1,000: roughly a billion operations versus a million. That’s the difference between a timeout and an instant answer — and between a monitoring dashboard that lags and one that updates live.

Fixed-size windows — the size-k template

When the problem hands you the window size (“any 7 days”, “every k elements”, “moving average over 5 readings”), the template is mechanical:

public class MaxWindowSum {
    public static void main(String[] args) {
        int[] txns = {4, 2, 9, 7, 1, 5};
        int k = 3;

        // 1. Build the first window honestly
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += txns[i];
        }
        int best = windowSum;

        // 2. Slide: subtract what leaves, add what enters
        for (int right = k; right < txns.length; right++) {
            windowSum += txns[right];        // enters on the right
            windowSum -= txns[right - k];    // leaves on the left
            best = Math.max(best, windowSum);
        }

        System.out.println("Best " + k + "-day total: " + best);
    }
}

Burn in the shape: pay full price once for window zero, then every later window costs two operations. Averages are the same template — divide windowSum by k when you read it, never re-sum.

Variable-size windows — grow and shrink

Harder problems don’t give you k. They give you a constraint and ask for the longest (or shortest) window that satisfies it: “longest substring without repeating characters”, “smallest subarray with sum at least 100”.

The mechanic becomes a caterpillar:

1. Grow the right edge one step at a time, adding the new element to the window’s state.
2. The moment the window becomes invalid (a repeat appeared, the sum overshot), shrink from the left until it’s valid again.
3. After every step, check if the current valid window beats your best.

flowchart LR
    A[Move right edge in] --> B{Window still valid}
    B -->|yes| C[Record best then grow again]
    B -->|no| D[Remove left edge element]
    D --> B
    C --> A

Both pointers only ever move forward. Each element enters the window once and leaves at most once — 2n pointer moves total, so it’s still O(n) even though there’s a loop inside a loop.

Here’s “Longest Substring Without Repeating Characters”, with the HashSet from Arrays & Hashing tracking what’s currently inside the window:

import java.util.HashSet;
import java.util.Set;

public class LongestUnique {
    public static void main(String[] args) {
        String s = "abcabcbb";

        Set<Character> window = new HashSet<>();
        int left = 0;
        int best = 0;

        for (int right = 0; right < s.length(); right++) {
            char entering = s.charAt(right);

            // shrink until the entering char has no duplicate inside
            while (window.contains(entering)) {
                window.remove(s.charAt(left));
                left++;
            }

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

        System.out.println("Longest run of unique chars: " + best); // 3 ("abc")
    }
}

The set IS the window’s contents. If the problem needs counts instead of presence (“longest substring with at most 2 distinct characters”), swap the HashSet for a HashMap<Character, Integer> — same skeleton, richer state.

The golden rule — and when the pattern refuses to work

The recognition signal, word for word: “longest / shortest / best CONTIGUOUS subarray or substring.” Contiguous is non-negotiable. The window is a physical chunk of the array; the answer must be a chunk.

Sliding window also quietly depends on something subtle: removing the left element must be cheaply undoable. Subtracting from a sum — trivial. Removing a char from a HashSet — trivial. But:

• “Maximum product subarray” with negative numbers — removing a negative can flip the sign of everything; the window state can’t be patched cheaply. Different technique.
• “Longest increasing subsequence” — subsequence means you can skip elements. There’s no contiguous chunk to slide. That’s dynamic programming territory (DP Intro).
• Any problem where shrinking the window might need to be reversed later — once a sliding window gives something up, it never goes back. If correctness needs backtracking, the window model is broken.

If you can’t answer “what do I subtract when the left element leaves?”, you don’t have a sliding window problem.

See It Move

Watch how the running sum changes by exactly two numbers per step — nothing in the middle is ever touched again.

Step through it and notice:

• The first window is the only one that gets fully summed — every later step is one subtract, one add.
• The left edge never moves backward. Neither pointer ever does.
• The middle elements of the window are never revisited — that’s where the O(n·k) cost went.
• The best-so-far only updates when the patched sum beats it; the window keeps sliding regardless.

Spot The Pattern

Where It Runs In Real Life

Rate limiters. “Max 100 API requests per user per 60 seconds” is a sliding window over time. Production gateways keep per-user counters for the current window; as time advances, old requests fall off the left edge and stop counting against the limit. Every payment API you’ll integrate with enforces exactly this.

Monitoring dashboards. That “avg response time, last 5 minutes” graph never re-sums five minutes of data points per refresh. It keeps a running aggregate and patches it — subtract expired points, add fresh ones. Same arithmetic you wrote above, running in Grafana-style systems all day.

TCP congestion control. The network protocol under every request you make literally has a “window”: the amount of unacknowledged data allowed in flight. As acknowledgements arrive, the window slides forward over the byte stream. The name of this pattern comes from networking, not LeetCode.

Trading and price systems. Moving averages (the 50-day line on every stock chart) are fixed-size windows over a price series. Computing them naively for thousands of instruments would melt the server; subtract-and-add keeps it linear.

Stream analytics. “Alert if more than 50 failed logins in the last 10 minutes” — fraud detection, log alerting, and event pipelines all aggregate over the last N events or seconds. The window slides; the aggregate gets patched, never rebuilt.

Build This

You’re building TxnWindow — a transaction analyzer that runs both templates, then you’ll sabotage it to feel why each line exists.

1. Create a folder txnwindow, and inside it TxnWindow.java:

import java.util.HashSet;
import java.util.Set;

public class TxnWindow {

    public static void main(String[] args) {
        int[] dailyTxns = {12, 5, 8, 20, 3, 9, 15, 7, 11, 2};

        System.out.println("Busiest 3-day stretch: " + maxKDaySum(dailyTxns, 3));
        System.out.println("Longest streak of distinct counts: " + longestDistinctStreak(dailyTxns));
    }

    // Fixed window: highest total over any k consecutive days
    static int maxKDaySum(int[] txns, int k) {
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += txns[i];
        }
        int best = windowSum;
        for (int right = k; right < txns.length; right++) {
            windowSum += txns[right] - txns[right - k];
            best = Math.max(best, windowSum);
        }
        return best;
    }

    // Variable window: longest run of days with no repeated txn count
    static int longestDistinctStreak(int[] txns) {
        Set<Integer> window = new HashSet<>();
        int left = 0;
        int best = 0;
        for (int right = 0; right < txns.length; right++) {
            while (window.contains(txns[right])) {
                window.remove(txns[left]);
                left++;
            }
            window.add(txns[right]);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

2. Compile and run:

javac TxnWindow.java
java TxnWindow

Confirm: busiest 3-day stretch prints 33. Now verify it by hand against the array — find which three consecutive days produce it. Doing that check yourself IS the exercise.

3. Break it — forget the subtraction. In maxKDaySum, delete - txns[right - k]. Recompile, run. The “window” now only grows — you’ve accidentally built a running total of everything. Watch the answer inflate. Put it back.

4. Break it — shrink with if instead of while. In longestDistinctStreak, change while to if. Run with the array {1, 2, 2, 2, 3}. The window keeps a duplicate inside because one shrink step wasn’t enough. This is the most common sliding window bug in interviews. Fix it back.

5. Extend it. Add minDaysToReach(int[] txns, int target) — the shortest contiguous stretch of days whose total is at least target. Grow right adding to a sum; while the sum is at least target, record the length and shrink left. Return -1 if no window ever reaches the target. Test with target 40.

6. Extend it again. Print the moving 3-day average for every position (the fixed template, divided by k). Now you’ve built the core of a monitoring dashboard metric.

Problems To Solve

The rule: solve until you can write both templates from memory. If stuck 25 minutes, read the approach, close it, re-solve from scratch — reading a solution you didn’t re-derive teaches nothing.

Check Yourself

1. What single word in a problem statement is the strongest sliding window signal?
2. Why is the sliding window O(n) when the brute force is O(n·k)? Where does the saving come from?
3. In the fixed-size template, which element gets subtracted when the window slides to index right?
4. In the variable-size template, when do you shrink from the left, and why is it a while and not an if?
5. Why is the variable window still O(n) even though there’s a while-loop inside the for-loop?
6. “Longest increasing subsequence” mentions “longest” — why is it NOT a sliding window problem?
7. What property must the window’s state have for the pattern to work when the left element leaves?
8. A rate limiter allows 100 requests per 60 seconds. Describe it as a sliding window: what enters, what leaves, what’s the state?

Explain it out loud: Face the empty chair and explain, using the [4, 2, 9, 7, 1, 5] array, why window 2’s sum can be computed from window 1’s in two operations — then explain when you’d reach for the variable version instead, and name one problem where a window flat-out cannot work. If you stumble on the last part, re-read the golden rule section.

Still Unclear?

Copy-paste any of these into Claude — they’re built to deepen understanding, not to do the work for you:

I'm learning the sliding window pattern in Java. Give me 5 one-line problem
descriptions, mixed between sliding window and NOT sliding window (DP,
two pointers, hash map). I'll answer which pattern each one is and why.
Check my answers and explain what wording gave each one away. Don't show
any code.

Walk me through why the variable-size sliding window is O(n) and not O(n^2),
even though it has a while-loop inside a for-loop. Use the idea of counting
total pointer movements, not loop nesting. Then quiz me on it.

Explain why maximum product subarray with negative numbers breaks the
sliding window pattern, while maximum sum subarray of size k does not.
Focus on what happens to the window state when the left element leaves.
No solutions — just the reasoning.

Why AI Can’t Do This For You

AI will write a flawless sliding window in one second — once someone tells it the problem IS a sliding window. The billable skill is the 30 seconds before that: reading “find the longest period where no customer ID repeats” in a vague Jira ticket and recognizing the contiguous-chunk shape under the business words. In an interview, that recognition happens with a person watching and no prompt box.

And in production, the cost of missing it is silent: the O(n·k) version also passes the tests — it just burns CPU recomputing overlaps forever, and the dashboard gets slower every month as data grows. AI won’t flag code that works. The engineer who sees the re-added overlap will.

Module done? Add it to today’s tracker