Sliding Window Problems Leave Clues. Read Them Right.

You understand how sliding window works. Two pointers, a window that expands right and contracts from the left, O(n) instead of O(n²). You've seen the picture with the blue bracket sliding across an array. Very satisfying. Very clear.

Then you see a new problem and spend six minutes wondering if it's a sliding window problem or a prefix sum problem or something else entirely. The algorithm is not the issue. Recognition is.

Nobody teaches pattern recognition directly. They teach the algorithm, give you three examples, and assume the rest will transfer. It mostly doesn't.

Four Phrases That Give It Away

Sliding window has a specific domain: find or optimize something over a contiguous subarray or substring, where validity depends on a local condition on the window's contents.

Four phrases signal it almost every time:

• "longest / shortest subarray or substring that..."
• "maximum / minimum sum over a window of size k"
• "find a contiguous subarray where..."
• any constraint phrase like "at most k distinct," "sum less than k," "all characters match"

When those appear, run this check: can I express the validity of a window as a condition that behaves predictably as the window grows or shrinks? Sum stays below a target. Distinct character count stays within a limit. Frequency of a character stays above a floor.

Then ask: if the window is currently invalid, does shrinking from the left always move me toward validity? If yes, you have a sliding window problem.

Two things that look similar but aren't: "find a pair that sums to k" is two pointers (you only care about the endpoints, not what's between them), and "count subarrays summing to exactly k" with negative numbers is a prefix sum problem. More on that below.

The Reason It Actually Works

Sliding window works because the validity condition is monotonic with respect to window growth. Once window [i, j] becomes invalid by expanding to j+1, every extension [i, j'] for j' > j+1 is also invalid. And once [i, j] is valid, shrinking to [i+1, j] keeps you valid or moves you closer to validity.

Think of it like a cart with a budget and a very strict return policy. If adding one more item pushes you over, adding more items definitely won't fix it. You have to put something back. That's the O(n) proof: each element enters the window once and leaves once. No backtracking. No revisiting.

The monotonicity requirement is also why negative numbers break the pattern for sum problems. If your array has negatives, adding the next element can decrease the total. A window that was invalid (sum > target) can become valid again as right advances, without any shrink from left. Monotonicity is gone. For "subarray sum equals k" with negatives (LeetCode 560), use a prefix sum with a hash map instead. The sliding window has nothing to offer you there.

Two Templates, Two Problem Shapes

Variable-window problems come in two shapes: maximize the window length, or minimize it. Using the wrong template is the most common implementation mistake, and it fails silently on most easy test cases, then explodes on the actual ones.

Max-length template (longest substring / subarray meeting a condition):

Shrink by exactly one when the window turns invalid, then update the result. The window size only ever grows or stays the same.

def max_length(s: str, k: int) -> int:
    left = 0
    count = {}
    result = 0
    for right in range(len(s)):
        # expand: add s[right] to state
        count[s[right]] = count.get(s[right], 0) + 1

        # shrink once if invalid
        if len(count) > k:
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1

        result = max(result, right - left + 1)
    return result

Example: Longest Substring with At Most K Distinct Characters. Expand right until you exceed k distinct characters, then nudge left by one. Result updates every iteration.

Min-length template (shortest substring / subarray meeting a condition):

Shrink while the window is valid, updating the result inside the shrink loop. You want to squeeze the window as small as possible each time it becomes valid.

def min_length(s: str, t: str) -> str:
    need = {}
    for c in t:
        need[c] = need.get(c, 0) + 1
    have, total = 0, len(need)
    window = {}
    left = 0
    best = (float('inf'), 0, 0)

    for right in range(len(s)):
        c = s[right]
        window[c] = window.get(c, 0) + 1
        if c in need and window[c] == need[c]:
            have += 1

        while have == total:        # window is valid: try to shrink
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            window[s[left]] -= 1
            if s[left] in need and window[s[left]] < need[s[left]]:
                have -= 1
            left += 1

    return s[best[1]:best[2]+1] if best[0] != float('inf') else ""

Example: Minimum Window Substring (LeetCode 76). Each time the window contains all required characters, tighten from the left before expanding further.

Fixed-window template (window of exactly size k) is the simplest case. No shrink condition needed: add the incoming element, subtract the outgoing one.

def fixed_window(nums: list, k: int) -> int:
    window_sum = sum(nums[:k])
    result = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        result = max(result, window_sum)
    return result

For max-length, update outside the shrink. For min-length, update inside. Swap them and you'll get answers that are confidently wrong on any input that isn't a toy example.

Three nested for-loops. The cat and your O(n²) solution react the same way.

Where Sliding Window Stops Working

Three cases where the pattern quietly betrays you.

Negative numbers with sum constraints. The pattern fails the moment adding an element can decrease validity. For subarrays summing to exactly k with negatives, use a prefix sum map: check if prefix_sum - k has been seen, add the current prefix sum. O(n), handles negatives, no window logic needed.

"Exactly k" conditions. If the validity condition is "exactly k distinct elements," sliding window breaks directly. Adding an element can move you from k-1 distinct (invalid) to k (valid) to k+1 (invalid) in sequence, and there's no single shrink direction that handles it. The decomposition trick in the next section fixes this.

Non-monotonic string comparison. Permutation in String (LeetCode 567) looks like a natural variable window problem, and it is, but the validity check (character frequencies match exactly) needs a fixed window of size len(s1), not a variable one.

Tested with negative numbers. That's also the specific thing that breaks sliding window sum problems.

Two Non-Obvious Tricks

Trick 1: Exactly(K) = AtMost(K) minus AtMost(K-1).

Any problem asking for subarrays with exactly K [something] can be solved by running at-most-K sliding window twice. Count subarrays with at most K distinct elements, subtract the count for at most K-1 distinct. The difference is exactly K.

def subarraysWithKDistinct(nums: list, k: int) -> int:
    def at_most(k: int) -> int:
        count = {}
        left = 0
        result = 0
        for right in range(len(nums)):
            count[nums[right]] = count.get(nums[right], 0) + 1
            while len(count) > k:
                count[nums[left]] -= 1
                if count[nums[left]] == 0:
                    del count[nums[left]]
                left += 1
            result += right - left + 1   # all subarrays ending at right
        return result

    return at_most(k) - at_most(k - 1)

The right - left + 1 term counts every subarray ending at right that starts somewhere in [left, right]. That's the counting primitive you need.

Trick 2: The max-count invariant in LC 424.

Longest Repeating Character Replacement (LeetCode 424) asks for the longest window where window_size - max_frequency <= k. When you shrink the window, you might think you need to recompute max_freq by scanning the frequency map. You don't.

Letting max_freq only increase, never decrease, is still correct for finding the maximum length. If max_freq becomes stale (slightly inflated after a shrink), the condition right - left + 1 - max_freq > k still forces a shrink whenever the window is genuinely invalid. The window never grows beyond a size that was valid at some point. For a max-length problem, that's fine.

def characterReplacement(s: str, k: int) -> int:
    count = {}
    max_freq = 0
    left = 0
    result = 0
    for right in range(len(s)):
        count[s[right]] = count.get(s[right], 0) + 1
        max_freq = max(max_freq, count[s[right]])
        # max_freq never decreases: intentional
        if (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1
        result = max(result, right - left + 1)
    return result

This drops the hidden O(26) cost of recomputing max_freq on every shrink. It surprises people the first time they see it pass. Then they feel slightly betrayed by how obvious it was in hindsight.

Practicing the full recognition-to-implementation loop out loud is where most people have the biggest gap. SpaceComplexity runs voice-based mock interviews where you have to narrate why you chose this pattern, walk through a worked example, and defend the complexity on the fly. That's where recognition under pressure actually gets built.

Recap

• Monotonicity is the core requirement. Expanding pushes toward invalidity; shrinking pushes toward validity. No backtracking needed.
• Max-length: update outside the shrink. Min-length: update inside the shrink loop.
• Negative numbers break sum-based windows. Use prefix sum with a hash map instead.
• Exactly(K) = AtMost(K) - AtMost(K-1). Converts a non-monotonic condition into two standard sliding windows.
• Max-count never needs to decrease in LC 424. Stale frequency is safe for max-length problems.
• Always update window state when shrinking. Forgetting to remove the departing element from your counter is the most common bug.

Further Reading

• Sliding Window Technique on GeeksforGeeks
• LeetCode 76: Minimum Window Substring
• LeetCode 239: Sliding Window Maximum
• LeetCode 424: Longest Repeating Character Replacement