Sliding Window — Subarray and Substring Problems Made Easy

Whenever a question asks for the longest, shortest or best contiguous subarray or substring, think sliding window. Instead of re-checking every possible subarray (O(n²) or worse), you keep a "window" [left, right] and slide it across the data, updating your answer in O(n).

Fixed-size window

Problem: the maximum sum of any k consecutive elements.

Re-adding k numbers for every position costs O(n·k). Instead, when the window slides one step, add the new element and subtract the one that left.

def max_sum_k(nums, k):
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]   # slide: in comes right, out goes right-k
        best = max(best, window)
    return best

Dry run — nums = [2, 1, 5, 1, 3, 2], k = 3:

window	sum
[2,1,5]	8
[1,5,1]	8 − 2 + 1 = 7
[5,1,3]	7 − 1 + 3 = 9 ← best
[1,3,2]	9 − 5 + 2 = 6

Variable-size window — the template

Most interview questions have a window whose size changes. The template:

1. Expand the window by moving right one step and adding nums[right].
2. While the window is invalid, shrink it by moving left and removing nums[left].
3. The window is now valid — update the answer.

def sliding_window(arr):
    left = 0
    state = ...                      # counts, sum, set — whatever describes the window
    best = 0
    for right in range(len(arr)):
        add arr[right] to state
        while window is invalid:
            remove arr[left] from state
            left += 1
        best = max(best, right - left + 1)
    return best

Each element enters the window once and leaves at most once → O(n) total, even with the inner while.

Example — Longest Substring Without Repeating Characters

The window is valid when it has no repeated character.

def length_of_longest_substring(s):
    seen = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in seen:            # invalid: shrink until ch is gone
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

int lengthOfLongestSubstring(String s) {
    Set<Character> seen = new HashSet<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char ch = s.charAt(right);
        while (seen.contains(ch)) seen.remove(s.charAt(left++));
        seen.add(ch);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Dry run — s = "abcabcbb": the window grows to "abc" (3); the next a forces left past the first a, giving "bca"; and so on. Answer: 3.

Example — Minimum Size Subarray Sum (shortest window)

Find the shortest subarray with sum ≥ target (all numbers positive). Here we shrink while the window is valid, recording the answer each time, because we want it as small as possible.

def min_subarray_len(target, nums):
    left = total = 0
    best = float('inf')
    for right, x in enumerate(nums):
        total += x
        while total >= target:           # valid → try to shrink
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float('inf') else best

Longest window: shrink while invalid, update after. Shortest window: shrink while valid, update inside.

Example — Max Consecutive Ones III

The longest run of 1s if you may flip at most k zeros: the window is valid while it contains ≤ k zeros. Same template; the state is "zeros in window".

When sliding window does NOT work

Sliding window relies on this: growing the window only makes the condition "more true" (or more false) — e.g. sums only increase when all numbers are positive. With negative numbers, a bigger window can have a smaller sum, so shrinking logic breaks. For "subarray sum equals k" with negatives, use prefix sums + hash map instead (see Arrays & Hashing).

How to recognise it

• "Longest / shortest / maximum / minimum subarray or substring…"
• "…with at most K distinct / at most K changes / no repeating…"
• Contiguous elements only (not subsequences).

Common mistakes

1. Updating the answer in the wrong place (inside vs after the while) — see the rule above.
2. Forgetting to remove arr[left] from the state when shrinking.
3. Window length off by one: it is right − left + 1.
4. Using it with negative numbers when the condition is a sum.

Key takeaways

• Fixed window: add the new element, subtract the outgoing one — O(n).
• Variable window: expand right, shrink left while invalid, update answer — O(n).
• The state (set, counts, sum) is what makes each problem different; the skeleton stays the same.