Introduction to Sliding Window

Find the max-sum window of size 1000 in a 100,000-element array. The obvious “sum each window” code does ~10⁸ operations — about a second. But 999 of every 1000 numbers are shared between consecutive windows. Stop re-adding them and the same problem takes ~10⁵ operations — a millisecond. That one observation is the sliding-window pattern.

The sliding window pattern lives at the intersection of two ideas:

1. The answer depends on a contiguous range of the input (a subarray, a substring, a window of size k).
2. As the range shifts by one element, most of its internal state stays the same — so you can update incrementally instead of recomputing.

When both are true, the brute-force O(n²) “try every subarray” approach collapses to O(n).

The brute-force baseline

Take a representative problem:

Given an array nums and integer k, find the maximum sum of any subarray of size k.

The obvious code:

def max_sum_brute(nums, k):
    best = float('-inf')
    for i in range(len(nums) - k + 1):
        s = sum(nums[i:i + k])
        best = max(best, s)
    return best

Outer loop: n − k + 1 starts. Inner sum call: O(k) each. Total: O(n × k). For n = 10^5 and k = 10^4, that’s 10^9 operations — minutes of wall-clock time.

But every shift looks like this:

[1, 4, 2, 10, 23, 3, 1, 0, 20]    k = 4

start i=0:  [1, 4, 2, 10]                                   sum = 17
start i=1:     [4, 2, 10, 23]                               sum = 39
start i=2:        [2, 10, 23, 3]                            sum = 38
start i=3:            [10, 23, 3, 1]                        sum = 37

Between i=0 and i=1, three of the four elements are identical. We’re paying O(k) to re-add 75% of the same numbers. That’s the waste.

The incremental update

The shift from window [i .. i+k−1] to [i+1 .. i+k] is two operations:

• Add the new element nums[i + k]
• Subtract the element that left, nums[i]

The running sum updates in O(1), regardless of how big k is:

int maxSum(vector<int>& nums, int k) {
    int n = nums.size();
    int window = 0;
    for (int i = 0; i < k; i++) window += nums[i];
    int best = window;
    for (int i = k; i < n; i++) {
        window += nums[i] - nums[i - k];     // add new, drop old
        best = max(best, window);
    }
    return best;
}

def max_sum(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]      # add new, drop old
        best = max(best, window)
    return best

public int maxSum(int[] nums, int k) {
    int window = 0;
    for (int i = 0; i < k; i++) window += nums[i];
    int best = window;
    for (int i = k; i < nums.length; i++) {
        window += nums[i] - nums[i - k];
        best = Math.max(best, window);
    }
    return best;
}

Time: O(n) — one pass. Space: O(1).

Recall the single line that is the whole pattern — slide the window in O(1):

def max_sum(nums, k):
  window = sum(nums[:k])               # first window, O(k) once
  best = window
  for i in range(k, len(nums)):
      # ??? slide the window: add entering, drop leaving
      best = max(best, window)
  return best

That’s the entire idea. Everything else is figuring out what running state to maintain (sum, count, hash map, deque, set) and when to record the answer (every shift, only when valid, only when invalid becomes valid).

The two flavors

Once you’ve seen a few sliding-window problems, you notice they split cleanly into two camps:

1. Fixed-size windows

The window has a hard length k. You know exactly when to slide (every iteration) and exactly when to record (every iteration once the first window is built).

Examples:

• Maximum sum of any size-k subarray
• Average of every contiguous size-k window (moving average)
• “Find all anagrams of p in s” (window length = len(p))
• “Does any size-k window contain a duplicate?”
• Sliding window maximum (the hardest fixed-window problem; uses a deque)

2. Variable-size windows

The window expands when the state is “valid” and contracts when it’s “invalid”. You track the longest, shortest, or count of valid windows seen so far.

Examples:

• Longest substring without repeating characters
• Smallest subarray with sum >= target
• Minimum window substring (smallest window of s containing all of t)
• Longest substring with at most k distinct characters
• Subarrays with at most / exactly k distinct integers

The mental shift between the two: fixed-size is one pointer plus a fixed offset; variable-size is two genuine pointers that move independently.

A pattern-spotting checklist

Before reaching for the template, run through these:

If you can answer all five, the code writes itself.

When sliding window is NOT the answer

The pattern fails when:

• The answer needs subsequences, not subarrays. Sliding window only handles contiguous ranges. Longest Common Subsequence, Longest Increasing Subsequence — those are DP territory.
• The property isn’t monotonic. Some problems (“find a subarray whose product is closest to X” with mixed signs) need different approaches.
• You need to enumerate all windows. Most sliding-window solutions only track the best window. If you need to list every valid one, the cost may already be O(n²) regardless.
• k is given as a range, not a fixed value. “All subarrays of size between a and b” might still fit, but typically needs more careful state.

A worked example: the brute force vs the slide

Let’s race the two approaches on a 100,000-element array with k = 1000:

1000× speedup, same correctness. That’s the trade — one cheap insight (incremental update) for three orders of magnitude.

Quick check

Sliding window is the array techniques of Day 2 crystallized into a named pattern. Next: fixed-size windows — the simpler half, where the window length is a constant k and the template is cleanest.