Sliding Window

At a glance

The instinct

Brute force over subarrays recomputes the same middle elements again and again. A sliding window keeps a running state (sum, counts, distinct total) for the current range [left, right] and updates it in O(1) as elements enter on the right and leave on the left. Because both pointers only move forward, each element is added once and removed at most once: O(n) total.

The pattern works only when the rule is monotone: if a window is valid, shrinking it keeps it valid (or growing it keeps it invalid). That property is what makes "shrink until it's fine again" correct.

Recognise it

Not this pattern if...

• The array has negative numbers and you need an exact sum: adding an element no longer guarantees the sum rises, so use Prefix Sum + hash map.
• Elements need not be contiguous (subsequence): think DP or greedy.
• You want the maximum sum of any subarray with no size or validity constraint: that is Kadane's Running Best.
• You need a pair from both ends of sorted data: that is Two Pointers (converging).

Memory hack

Say it out loud in the interview:

1. "What state do I keep for the window (sum, count array, distinct counter)?"
2. "What makes the window invalid, and is that rule monotone so shrinking fixes it?"
3. "Do I record the answer after shrinking (longest) or while shrinking (shortest)?"

How it works

Every step: add s[right] to the state; while the window is invalid, remove s[left] and advance left; then update the answer. For "shortest valid" problems, flip it: while the window is valid, record its length and then shrink.

Trace for Longest Substring Without Repeating Characters on "abcabcbb":

flowchart LR
  A["right++ : add element to state"] --> B{"Window invalid?"}
  B -- yes --> C["remove nums[left], left++"]
  C --> B
  B -- no --> D["update answer with right - left + 1"]
  D --> A

In Longest Repeating Character Replacement, the window is valid while length - maxFreq <= k. In Minimum Window Substring, keep a missing counter of required characters; the window is valid when it hits zero.

Java template

class SlidingWindowToolkit {
    // Fixed size k: slide one step, adjust state in O(1).
    static long bestFixedWindow(int[] nums, int k) {
        long sum = 0, best = Long.MIN_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];                       // element enters
            if (right >= k) sum -= nums[right - k];   // element leaves
            if (right >= k - 1) best = Math.max(best, sum);
        }
        return best;
    }

    // Variable size, longest valid window (shrink while invalid, then record).
    static int longestValid(String s, int k) {
        int[] count = new int[128];
        int left = 0, distinct = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            if (count[s.charAt(right)]++ == 0) distinct++;    // add to state
            while (distinct > k) {                            // problem-specific invalid rule
                if (--count[s.charAt(left)] == 0) distinct--; // remove from state
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }

    // Variable size, shortest valid window (record while valid, then shrink).
    static int shortestWithSumAtLeast(int[] nums, int target) {
        int left = 0, best = Integer.MAX_VALUE;
        long sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {                           // valid: try to shrink
                best = Math.min(best, right - left + 1);
                sum -= nums[left++];
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

Complexity

• Time O(n): right moves n times, left moves at most n times in total, even with a nested while.
• Space O(1) for sums, or O(Σ) for a count array over the alphabet (constant for ASCII), O(k) for a hash map of distinct keys.
• Substring with Concatenation of All Words runs one window per offset 0..wordLen-1, giving O(n · wordLen) overall.

Variations

• Fixed window: size is given. Maximum Average Subarray I, Maximum Sum of Distinct Subarrays With Length K.
• Fixed window with frequency match: compare counts against a pattern. Find All Anagrams in a String, Permutation in String.
• Longest valid (shrink while invalid): Longest Substring Without Repeating Characters, Max Consecutive Ones III, Longest Repeating Character Replacement.
• Shortest valid (shrink while valid): Minimum Size Subarray Sum, Minimum Window Substring.
• Exactly K via at-most: atMost(K) - atMost(K - 1) counts subarrays with exactly K distinct values or K odd numbers.
• Word-level windows: step by word length instead of by character. Substring with Concatenation of All Words.
• Window with a monotonic deque: sliding window maximum keeps candidate indices in decreasing order.

Common mistakes

• Using if instead of while when shrinking, so the window can stay invalid for several steps.
• Updating the answer before the window has been repaired (longest) or after it has been broken (shortest).
• Forgetting to undo the state when left moves (decrement counts, adjust the distinct counter).
• Off-by-one window length: it is right - left + 1.
• In fixed windows, recording before the first full window exists (right < k - 1).

All practice problems

10 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.