Sliding Windows: The Core Idea

A sliding window keeps a running summary of one contiguous stretch of the input: a sum, a set of characters, a count of each letter. When the stretch moves by one position, you repair the summary by one element instead of rebuilding it from scratch.

That one change is the difference between checking every subarray, which is O(n²) or O(n³), and a single O(n) pass. Almost every "longest substring", "shortest subarray" or "every window of size k" question in an interview is this pattern.

The intuition: a moving seven-day total

A shop wants its sales total for every seven-day stretch of the year. The slow way adds up seven days for each stretch: 359 stretches × 7 additions. The quick way notices that Monday-to-Sunday and Tuesday-to-Monday share six days. To move the stretch forward one day, add the new day and subtract the day that fell off the back. That is two operations per step, however long the stretch is.

Now suppose the question changes to "the longest run of days where total sales stayed under ₹50,000". The stretch is no longer a fixed size. You grow it at the front while it stays under the limit, and when it goes over, you drop days from the back until it is under again. The front and back both only move forward. That is a variable-size window.

How to recognise it

• "Subarray" or "substring". Both mean contiguous. This is the most reliable signal. "Subsequence" and "subset" allow gaps, and those are dynamic programming or backtracking problems, not windows.
• A longest, shortest or count question about those stretches. "The longest substring with at most two distinct characters." "The shortest subarray whose sum is at least 7." "How many subarrays contain exactly k different values."
• A fixed size is named. "Every window of length k", "the best average of k consecutive days". This is the easy form.
• The brute force is "check every subarray". There are n(n + 1)/2 of them. With n up to 10⁵, that is 5 × 10⁹ subarrays, far too many. An O(n) or O(n log n) answer is expected, and a window is the usual one.

Before committing, check the values. A window on sums needs non-negative numbers. If the constraints say values can be negative, a sum-based window is wrong, and you need prefix sums (or Kadane's algorithm for a maximum sum). Character-count windows have no such problem.

How it works: two boundaries and one summary

Keep two indices, start and end, and a summary that always describes exactly the elements from start to end. The loop has three steps:

1. Expand — move end right by one and add the entering element to the summary.
2. Shrink — while the window breaks the rule, remove the element at start from the summary and move start right.
3. Record — the window now obeys the rule, so update the answer from it.

A full trace makes it concrete. Problem: the longest substring with no repeated character. Input: "abba". Summary: the set of characters in the window. The rule breaks when the entering character is already in the set.

The answer is 2. Look at end = 2: the shrink ran twice before the window was legal again. That is why the shrink is a while, never an if.

Why it is correct, and why it is O(n)

Correct. Moving start right is safe because of one property: if the window from start to end breaks the rule, then every longer window that contains it also breaks the rule. If "abb" has a repeat, so does "abba". So once a start position fails for some end, it can never be part of a better answer later, and it never needs to be revisited. This "breaking the rule only gets worse as the window grows" property is what every window problem needs. It is exactly what negative numbers destroy in a sum.

O(n). The inner while looks as if it could make the loop O(n²). It cannot. start never moves left, so across the whole run it moves right at most n times in total. end moves right exactly n times. That is at most 2n moves, each doing O(1) work on the summary. This way of counting, adding up the total work over the whole run instead of bounding each step, is called amortised analysis. It appears again with monotonic stacks, where each element is pushed once and popped once.

Variants: the shapes a window takes

The summary is either numeric (a running sum, a count of zeros) or structural (a set, or a map of counts). A count map is what you need when the window's contents matter, as in Permutation in String.

The templates

Fixed size. Build the first window once, then slide.

1def max_sum_of_k(nums: list[int], k: int) -> int:2    """Largest sum of any k consecutive values. Assumes 1 <= k <= len(nums)."""3    window_sum = sum(nums[:k])                    # first window: O(k), once4    best = window_sum5    for end in range(k, len(nums)):6        window_sum += nums[end] - nums[end - k]   # one enters, one leaves7        best = max(best, window_sum)8    return best

When end is the entering index, the window covers end − k + 1 to end, so the element that just left is at end − k. Derive that each time rather than memorising it.

Longest valid window. Here "valid" means "at most k distinct characters", but only the while condition changes from problem to problem.

1def longest_with_at_most_k_distinct(text: str, k: int) -> int:2    """Length of the longest substring with at most k distinct characters."""3    counts: dict[str, int] = {}4    start = 05    best = 06    for end, char in enumerate(text):7        counts[char] = counts.get(char, 0) + 1     # 1. expand8        while len(counts) > k:                     # 2. shrink while INVALID9            leaving = text[start]10            counts[leaving] -= 111            if counts[leaving] == 0:12                del counts[leaving]                # or len(counts) over-counts13            start += 114        best = max(best, end - start + 1)          # 3. record AFTER the loop15    return best

Line by line: the entering character is counted; while there are too many distinct characters, the character at start is removed (and its key deleted when it reaches zero, so len(counts) stays honest) and start moves on; the window is now valid, so its length is a candidate.

Shortest valid window. Flip the loop: shrink while the window is still valid, recording inside, to find the smallest window that works.

1def min_subarray_len(target: int, nums: list[int]) -> int:2    """Length of the shortest subarray with sum >= target (positive numbers), or 0."""3    start = 04    window_sum = 05    best = float("inf")6    for end, value in enumerate(nums):7        window_sum += value8        while window_sum >= target:          # still valid: record, then try smaller9            best = min(best, end - start + 1)10            window_sum -= nums[start]11            start += 112    return 0 if best == float("inf") else best

On target = 7, nums = [2, 3, 1, 2, 4, 3], the sum first reaches 8 at end = 3 (window [2, 3, 1, 2], length 4). At end = 4 it shrinks through lengths 4 and 3. At end = 5 it shrinks through [2, 4, 3] (length 3) to [4, 3] (sum 7, length 2). The answer is 2.

Complexity

All three templates run in O(n) time: each index enters once and leaves at most once. The fixed window also spends O(k) building the first window, which is within O(n). Space is O(1) for a numeric summary, and O(d) for a set or count map, where d is the number of distinct values the window can hold. For lowercase letters d ≤ 26, so that is O(1) too.

Where it goes wrong

1. if instead of while in the shrink. It removes one element when several may be needed. On "abba" the longest-unique-substring code then returns 3 instead of 2. On "abcabcbb" it still returns 3, the right answer, so the bug hides on the example most people test first.
2. Recording at the wrong moment. In a longest problem, record after the shrink loop, when the window is valid. In a shortest problem, record inside it, before each removal. Mixing them measures windows that are invalid or already broken.
3. Not cleaning up the leaving element. Decrementing a count without deleting the zero key makes len(counts) over-report the distinct count, so the window shrinks too far. Removing the entering character instead of text[start], or moving start without touching the summary, leaves the summary describing a window that no longer exists.
4. Using a window where none applies. A sum with negative numbers breaks the "only gets worse as it grows" property. A "subsequence" is not contiguous. Both need a different pattern.