Sliding Window Patterns

Stop re-adding what you already added

A heart-rate monitor records one reading per second for a week: 604,800 numbers. Which hour, meaning 3,600 consecutive readings, had the highest average?

The obvious plan sums every possible hour from scratch. There are 604,800 − 3,600 + 1 = 601,201 of them, and each one costs 3,600 additions. That is 2,164,323,600 additions, over two billion.

Now look at two neighbouring hours. They share 3,599 readings. Sliding one second later drops one reading on the left and adds one on the right, so you can update the sum with those two numbers instead of re-adding the other 3,599. The whole week then costs 3,600 + 2 × 601,200 = 1,206,000 operations, about 1,800 times less work for the same answer.

That is the whole idea of a sliding window: keep a summary of a contiguous range and update it at the edges instead of rebuilding it. When the size is not fixed, the same trick still works as long as the condition behaves predictably when the window grows or shrinks. Then both edges only ever move forward, and the whole scan is linear. This lesson teaches five moves, and also how to tell when a window will quietly give you a wrong answer.

You should already be comfortable with Foundation: Arrays & Strings: running summaries, sets and count vectors, and prefix sums. A window is a pair of same-direction pointers, the family covered in Two Pointer Techniques. That lesson helps, but you don't need it first.

The window's contract

A window is a subarray (or substring): contiguous, no gaps. This lesson writes it as nums[left..right] with both ends inclusive, so

• its length is right - left + 1;
• in Python it is the slice nums[left:right + 1];
• it is empty when left == right + 1. That happens on purpose, for example in Move 4, where the loop can shrink a window down to nothing.

Alongside the two indices you keep the window state: a sum, a count, a dictionary, whatever the question needs. The state must always describe exactly the elements between left and right. Every time right moves, you add nums[right] to the state. Every time left moves, you remove nums[left] first. Forget either half and the state stops describing the window, and every decision based on it goes wrong.

Both indices only move right. Each index enters the window once and leaves at most once, so there are at most 2n edge moves in total. That fact is where every O(n) bound in this lesson comes from.

How is this different from the converging pointers of Two Sum II? There, the pointers start at opposite ends and move toward each other, and the state is just the pair at the two ends. Nothing between them is summarised. A window's state covers every element between its edges.

💡 Debugging habit: while developing, assert that the state matches a from-scratch recount, e.g. assert counts == Counter(s[left:right + 1]). It fails at the exact step the state drifts. Delete it before you submit, because the recount costs O(window) each time.

Move 1: Add what enters, undo what leaves

Smell: "every k consecutive", "window of size k", and slow code that re-sums each block.

The fixed-size frame

LeetCode 643: Maximum Average Subarray I gives you nums and k (with 1 <= k <= n <= 10^5; values can be negative) and asks for the largest average of any k consecutive elements. Since every window has the same length, the largest average belongs to the largest sum. Find the best sum and divide once at the end.

Predict first: in nums = [2, 1, 5, 1, 3, 2] with k = 3, how many windows are there? The first one sums to 8. Without adding three numbers, what does the next one sum to?

The slow version recomputes each window:

def max_window_sum_slow(nums, k):
    best = float('-inf')
    for start in range(len(nums) - k + 1):
        best = max(best, sum(nums[start:start + k]))   # k additions, every time
    return best

That is (n − k + 1)·k additions, and each slice also copies k values. What does it repeat? Neighbouring windows share k − 1 elements, and it adds all of them again.

The cost depends on k in a way people often get wrong. With k = 3 it is about 3n, which is fine. With k = n there is one window and n additions, also fine. The product (n − k + 1)·k peaks near k = n/2: for n = 100,000 and k = 50,000 it is 2,500,050,000 additions. So the window matters when k grows with n, not when k is tiny.

The fast version keeps one running sum and fixes it up at the edges:

def max_window_sum(nums, k):
    # contract: 1 <= k <= len(nums)
    window = sum(nums[:k])            # first window: indices 0..k-1
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]   # nums[right] enters, nums[right - k] leaves
        best = max(best, window)
    return best

def find_max_average(nums, k):
    return max_window_sum(nums, k) / k

Trace [2, 1, 5, 1, 3, 2] with k = 3:

Why the index is right - k

Invariant: after the update at step right, window is the sum of nums[right - k + 1 .. right]. Before the update it covered nums[right - k .. right - 1]. Adding nums[right] moves the right edge. Subtracting nums[right - k], the element exactly k behind the one entering, moves the left edge. The new left edge is right - k + 1. So the element that leaves is at right - k, one position before the new left edge.

Cost. k additions for the first window, then 2 operations for each of the n − k slides: k + 2(n − k) = 2n − k. That is O(n) time and O(1) extra space. On the six-element example it is 9 operations against the slow version's 12.

Edge cases and traps

• Start best at the first window, not at 0. On [-3, -1, -2] with k = 2 the windows sum to −4 and −3, so the answer is −3. A best = 0 start returns 0, which is the sum of no window at all.
• The slide starts at right = k, because the first window already used indices 0..k−1.
• ⚠️ Python won't catch a boundary slip. If you build the first window with range(k - 1) (one element short) and start the slide at k - 1, the first slide subtracts nums[-1]. Python quietly reads the last element instead of raising an error, and every later window is off by that value. Java would at least throw an exception on index −1.
• k > n has no window at all, and sum(nums[:k]) silently sums fewer than k values. LeetCode promises k <= n. If your problem doesn't, decide the contract first (return None? raise?).
• Negative numbers are fine here. The size is fixed, so there is no shrink decision to get wrong. Variable-size windows (Moves 3–5) are where negatives start to hurt.

Which summaries can slide?

Anything with an exact undo:

The product row is a trap. If a 0 enters, the product becomes 0 and the other values in the window are lost; dividing by that 0 when it leaves raises ZeroDivisionError. Python's / also turns the product into a float, and floats cannot hold every integer above 2⁵³ (about 9·10¹⁵), so a long-running product drifts. Keep a separate count of zeros and multiply only the non-zero values, and use // so that dividing out a factor you multiplied in stays exact.

The letter-count row is how you slide a window of length len(p) across a string to find anagrams of p. String Permutations works that through for Permutation in String.

Your turn: LeetCode 219: Contains Duplicate II. Return True if two different indices i and j have nums[i] == nums[j] and abs(i - j) <= k. What window do you slide, and what state does it need? Predict the results for ([1, 2, 3, 1], 3), ([1, 0, 1, 1], 1), ([1, 2, 3, 1, 2, 3], 2) and ([1, 1], 0).

def contains_nearby_duplicate(nums, k):
    window = set()                     # values at the previous k indices
    for i, x in enumerate(nums):
        if x in window:
            return True
        window.add(x)
        if len(window) > k:            # keep at most k values
            window.remove(nums[i - k])
    return False

Move 2: No undo? Keep the candidates

Smell: a fixed window, but the question is the maximum (or minimum) of each window. You can fold a new value into a running max in O(1). When the max itself leaves, you have nothing to fall back on except a rescan.

When the champion leaves

LeetCode 239: Sliding Window Maximum asks for the maximum of every length-k window (1 <= k <= n <= 10^5). Here is the tempting shortcut:

def running_max(nums, k):
    best = max(nums[:k])
    out = [best]
    for right in range(k, len(nums)):
        if nums[right] > best:
            best = nums[right]
        out.append(best)
    return out

Predict first: what does running_max([5, 1, 1, 1], 2) return? And why does the same function return the right answer on LeetCode's example [1, 3, -1, -3, 5, 3, 6, 7] with k = 3?

The honest slow version takes max of every window: O(n·k), up to about 2.5 billion comparisons at n = 10⁵ and k = n/2. A max-heap of (value, index) pairs also works in O(n log n): before reading the top, pop it while its index has left the window. Discarding by value instead would throw away copies that are still inside. Heaps & Priority Queues covers heaps. You can do better than both.

Younger and taller wins

Here is the insight. Suppose index i < j, both inside the window, and nums[i] <= nums[j]. Then nums[i] can never be the maximum of this or any later window. Every later window that still contains i also contains j, because j leaves later, and nums[j] is at least as big. So you can throw i away the moment j arrives.

After throwing away every dominated index, the survivors, from oldest to newest, have strictly decreasing values. The oldest survivor is the current maximum. Keep the survivors in a deque (double-ended queue), which gives O(1) pops at both ends:

from collections import deque

def max_sliding_window(nums, k):
    dq = deque()      # indices; their values strictly decrease from front to back
    out = []
    for right, x in enumerate(nums):
        if dq and dq[0] == right - k:          # the front index just left the window
            dq.popleft()
        while dq and nums[dq[-1]] <= x:        # older and not larger: can never be a max again
            dq.pop()
        dq.append(right)
        if right >= k - 1:                     # the first full window ends at k - 1
            out.append(nums[dq[0]])
    return out

Only one index leaves per step: right - k. If it survived, it is the oldest survivor, so it sits at the front. Trace [1, 3, -1, -3, 5, 3, 6, 7] with k = 3:

At right = 3 the deque holds three indices. The −1 and −3 aren't maxima yet, but they might be once the 3 leaves, so they stay. At right = 4 the 3 expires and the 5 arrives, and the 5 dominates everything older.

Why it works, and what it costs

Invariant: after step right, dq holds indices of the current window in increasing order with strictly decreasing values, and every window index missing from dq is dominated by a later, not-smaller value that is still in the window. So the maximum is always at dq[0].

The while loop inside the for loop looks quadratic, but it isn't. Each index is appended once and removed at most once, from one end or the other. That is at most 2n deque operations over the whole run: O(n) time, or amortized O(1) per step. The deque never holds more than k indices, so it uses O(k) extra space. The output list adds n − k + 1 values on top.

Traps

• Store indices, not values. A value alone can't tell you whether it has left the window, especially when values repeat.
• <= versus < in the pop. Popping ties (<=) keeps only the newest copy, which stays in the window longest. Popping only smaller values (<) keeps duplicates in the deque. Both are correct, because expiry is decided by index.
• First output at right = k - 1, not at k. With k = 1 the output is just nums.

🧠 The same "drop dominated candidates" idea with a plain stack and no expiry answers next greater element questions. That's the monotonic stack. The deque adds one thing: candidates also expire from the old end.

Your turn: adapt max_sliding_window into min_sliding_window. Which single line changes? Predict the output for ([4, 2, 12, 11, -5], 2).

        while dq and nums[dq[-1]] >= x:        # older and not smaller
            dq.pop()

Move 3: Longest window: grow, and shrink while broken

Smell: "longest (or maximum-length) contiguous … with at most …". Adding elements can break the condition, and removing elements heals it.

The fruit picker

LeetCode 904: Fruit Into Baskets tells a story: you walk along a row of trees and pick one fruit from each, starting anywhere; you have two baskets, each holding a single fruit type; you stop at the first tree whose type fits neither basket. Strip the story and it asks for the longest subarray with at most 2 distinct values. The general version, at most k distinct characters, is the running example here.

Predict first: what is the longest substring of "eceba" with at most 2 distinct characters? Is "eba" also an answer?

The slow version tries every start and extends to the right, which is O(n²) windows. Look at what it repeats. Once s[l..r] has too many distinct characters, every longer window starting at l does too, because it contains s[l..r]. The slow code keeps extending anyway. Then it moves to l + 1 and rebuilds its counts from nothing.

The property that makes it work

Call a condition shrink-closed if every valid window's smaller sub-windows are valid too. Equivalently: once a window is invalid, extending it keeps it invalid. "At most k distinct", "at most k zeros", "no repeated character" and "sum at most S with non-negative values" are all shrink-closed.

For each right edge, let L(right) be the smallest start that makes [L(right)..right] valid (or right + 1, the empty window, if no start does). Shrink-closure forces L to never decrease. If [l..right+1] is valid, then its sub-window [l..right] is valid too, so L(right) <= L(right + 1). So left never has to move back. That gives the template:

def longest_at_most_k_distinct(s, k):
    counts = {}                   # char -> how many times it occurs in s[left..right]
    left = 0
    best = 0
    for right, ch in enumerate(s):
        counts[ch] = counts.get(ch, 0) + 1          # 1. let s[right] in
        while len(counts) > k:                      # 2. shrink until valid again
            out = s[left]
            counts[out] -= 1
            if counts[out] == 0:
                del counts[out]                     # keeps len(counts) == distinct count
            left += 1
        best = max(best, right - left + 1)          # 3. valid here: record
    return best

Trace "eceba" with k = 2:

At right = 3 one removal is not enough: dropping the first e leaves ceb, still three distinct characters. That's why the shrink is a while.

Why it's correct. After step 2, [left..right] is the longest valid window ending at right: left is exactly L(right). Every candidate answer ends at some right, and step 3 sees each of those best windows once.

Cost. right moves n times and left moves at most n times in total, over the whole run rather than per step. So the inner loop body runs at most n times altogether: O(n) time, with expected O(1) dictionary operations. counts never holds more than k + 1 keys, so O(k) extra space.

Keep the mirror honest

• The del matters. len(counts) must mean "distinct characters in the window". Leave a zero-count key behind and len never drops, so the while keeps running. left runs past right and the code crashes: KeyError when it decrements a character that was never added, or IndexError when left runs off the end.
• Update the state on every shrink. A loop whose body is just left += 1 never changes len(counts), so it never ends.
• Record after the loop, not before. Before the while runs, the window may be invalid, and its length is not an answer.
• best = 0 is a real answer. With k = 0 the loop empties the window every time (left == right + 1) and the result is 0.

💡 You'll see editorials that write if instead of while here. That version moves left at most one step per right, so the window never gets shorter. It may stay invalid for a while, but it only grows while valid, so its length still ends at the right answer. It's a legitimate trick, but the window it leaves you with isn't guaranteed to be valid. That breaks anything that needs the window itself, including the counting in Move 5. Learn the while version first.

A variation: with non-negative values you can find the longest window whose sum is exactly S. Keep the shrink-closed condition "sum ≤ S", and after the loop check whether the sum equals S. If any window ending at right hits S exactly, the longest valid window ending there is it.

Longest Substring Without Repeating Characters is this move with the condition "no character twice". It has its own lesson, including a faster way to move left using last-seen indices.

Test it like a professional

A brute-force reference that is obviously correct, plus a few hundred random small inputs, catches most window bugs:

import random

def longest_brute(s, k):
    best = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            if len(set(s[i:j + 1])) <= k:
                best = max(best, j - i + 1)
    return best

for _ in range(500):
    s = ''.join(random.choice('abc') for _ in range(random.randint(0, 10)))
    k = random.randint(0, 3)
    assert longest_at_most_k_distinct(s, k) == longest_brute(s, k), (s, k)
print("all matched")

Use a small alphabet. Three letters make "too many distinct characters" happen often, which is exactly the path you want to exercise.

Your turn: LeetCode 1004: Max Consecutive Ones III. Given a 0/1 array and k, return the longest run of 1s you can make by flipping at most k zeros. What is the condition, and what is the smallest state that answers it? Predict ([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2) and ([0, 0, 0], 0).

def longest_ones(nums, k):
    zeros = 0
    left = 0
    best = 0
    for right, x in enumerate(nums):
        if x == 0:
            zeros += 1
        while zeros > k:
            if nums[left] == 0:
                zeros -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Move 4: Shortest window: shrink while it still works

Smell: "shortest (or minimum-length) contiguous … with sum at least … / containing all …". Here it's the other way round. Adding elements helps, and removing them can break the condition.

Minimum Size Subarray Sum

LeetCode 209: Minimum Size Subarray Sum: given a target and an array of positive integers, return the length of the shortest subarray whose sum is at least the target, or 0 if there is none.

Predict first: what is the answer for target 7 and [2, 3, 1, 2, 4, 3]? And what goes wrong if you reuse Move 3's loop, which shrinks while the window is invalid?

This condition is extension-closed: if a window is valid, every window containing it is valid too. That holds for "sum ≥ target" when values are non-negative, and for "contains every letter of t". The template mirrors Move 3:

def min_subarray_len(target, nums):
    # needs every nums[i] >= 0 (LeetCode 209 guarantees positive values)
    left = 0
    window = 0
    best = float('inf')
    for right, x in enumerate(nums):
        window += x
        while window >= target:                 # valid: record it, then try a shorter one
            best = min(best, right - left + 1)
            window -= nums[left]
            left += 1
    return 0 if best == float('inf') else best

Trace target 7 and [2, 3, 1, 2, 4, 3]:

Why it's correct. For a fixed right, the loop tries starts left, left + 1, … and records each while the window is still valid. It stops at the first invalid start, and every later start is invalid too: with non-negative values, dropping more elements can't raise the sum. Could the next right need a start before the current left? No. Each start the loop passed had already been recorded ending at right or earlier, and pairing it with a later right edge only gives a longer window. So left never moves back. O(n) time, O(1) extra space.

Moves 3 and 4 are mirror images. Before you write the loop, decide which one you have:

Traps

• Record before you remove. Record after left += 1 and you measure a window that has just lost an element. It may already be invalid, and then its length isn't an answer.
• while, not if. One big value can make several removals possible at once. An if removes one element per step and misses them. On target 7 and [1, 1, 1, 1, 7] the if version returns 5, but [7] alone works.
• >=, not >. A sum exactly equal to the target counts.
• No valid window: return what the contract says (0 here), never inf.

Boss level: Minimum Window Substring

LeetCode 76: Minimum Window Substring: return the shortest substring of s that contains every character of t, counting repeats (t = "AAB" needs two A's). Return "" if there is none. The classic example is s = "ADOBECODEBANC", t = "ABC", answer "BANC". The strings can have up to 10⁵ characters.

"Contains everything t needs" is extension-closed, so this is Move 4. The new difficulty is checking validity cheaply. Comparing two count tables on every step costs time proportional to the alphabet. Instead, keep one number:

• need[c]: how many copies of c the window must contain.
• have[c]: how many it currently contains (only for characters t uses).
• satisfied: how many distinct characters currently meet their quota. The window is valid exactly when satisfied == required, where required = len(need).

satisfied changes only when a count crosses its quota: it goes up when have[c] climbs to exactly need[c], and down when have[c] is about to fall below it.

from collections import Counter

def min_window(s, t):
    if not t:
        return ""              # nothing required: the empty window wins
    need = Counter(t)          # char -> copies required
    required = len(need)       # distinct chars whose quota must be met
    have = {}                  # char -> copies inside s[left..right] (needed chars only)
    satisfied = 0              # how many distinct chars currently meet their quota
    best_len, best_left = float('inf'), 0
    left = 0
    for right, ch in enumerate(s):
        if ch in need:
            have[ch] = have.get(ch, 0) + 1
            if have[ch] == need[ch]:               # quota just reached
                satisfied += 1
        while satisfied == required:               # valid: record, then try shorter
            if right - left + 1 < best_len:
                best_len, best_left = right - left + 1, left
            out = s[left]
            if out in need:
                if have[out] == need[out]:         # about to drop below quota
                    satisfied -= 1
                have[out] -= 1
            left += 1
    return "" if best_len == float('inf') else s[best_left:best_left + best_len]

Predict first: on "ADOBECODEBANC" / "ABC", what is the first valid window the scan meets? Later the scan reaches "CODEBA", also length 6. Does it replace the best?

The loop body only runs at three right edges. Everywhere else the window isn't valid, and only the expand lines run:

Cost. Each index enters once and leaves at most once, and building need reads t once: O(|s| + |t|) time. need and have only store characters that appear in t, so the extra space is O(u), where u is the number of distinct characters in t. That's at most 52 for English letters. If you also counted characters of s that t doesn't use, the table would grow to every distinct character of s for nothing.

⚠️ Forget satisfied -= 1 and satisfied never drops. The while loop can't stop, left runs off the end of s, and s[left] raises IndexError at the first valid window.

Edge cases: t longer than s returns "", because satisfied never reaches required. Matching is case-sensitive. An empty t needs the guard at the top: with required = 0, every window, even the empty one, would count as valid, and the loop would run off the end.

Your turn: predict min_window for ("a", "aa"), ("aa", "aa"), ("ab", "b") and ("bba", "ab"). Then: if the quota test read have[ch] >= need[ch] instead of ==, what would min_window("AAB", "AB") return?

Move 5: Count the windows, not just the best one

Smell: "count the subarrays such that …", or "how many contiguous …".

Every start at once

Take a shrink-closed condition. After Move 3's loop, [left..right] is the longest valid window ending at right, and every shorter window ending there is valid too: [left..right], [left+1..right], …, [right..right]. That's right - left + 1 new valid subarrays, and each valid subarray is counted exactly once, at its own right end.

LeetCode 713: Subarray Product Less Than K counts subarrays whose product is strictly less than k, with every nums[i] >= 1. Because no value is below 1, removing one can't raise the product, so "product < k" is shrink-closed. And because there are no zeros, dividing out the leaving value is exact.

Predict first: how many subarrays of [10, 5, 2, 6] have a product below 100?

def count_product_below(nums, k):
    # nums[i] >= 1, so shrinking never raises the product
    if k <= 1:
        return 0
    product = 1
    left = 0
    count = 0
    for right, x in enumerate(nums):
        product *= x
        while product >= k:
            product //= nums[left]          # exact: nums[left] is a factor of product
            left += 1
        count += right - left + 1           # windows [left..right], [left+1..right], ..., [right..right]
    return count

The k <= 1 guard isn't decoration. Every product is at least 1, so nothing qualifies. Without the guard, the while would empty the window and keep dividing by values that were never multiplied in. O(n) time, O(1) extra space.

Counting with an at-least condition. For an extension-closed condition, run Move 4's loop and add left instead of right - left + 1. When the loop stops, [left..right] is invalid, and so is every shorter window ending at right. Every start before left gives a valid window: left only moved past a start after that start had formed a valid window ending at right or earlier, and extending a valid window keeps it valid. On [3, 4, 1] with "sum ≥ 7" this counts [3, 4] and [3, 4, 1]: 2. The alternative is the complement: total subarrays minus those with sum < 7.

"Exactly K" is two "at most"s

Exactly K distinct is not monotone in either direction. [1, 2] has exactly 2 distinct values; cut it to [1] and it has 1, extend it to [1, 2, 3] and it has 3. No single window can track it. But every window with at most K distinct values has either at most K − 1, or exactly K. So

exactly(K) = atMost(K) − atMost(K − 1)

and both terms are shrink-closed counting windows. This is LeetCode 992: Subarrays with K Different Integers:

def at_most_distinct(nums, k):
    if k < 0:
        return 0
    counts = {}
    left = 0
    total = 0
    for right, x in enumerate(nums):
        counts[x] = counts.get(x, 0) + 1
        while len(counts) > k:
            counts[nums[left]] -= 1
            if counts[nums[left]] == 0:
                del counts[nums[left]]
            left += 1
        total += right - left + 1
    return total

def exactly_distinct(nums, k):
    return at_most_distinct(nums, k) - at_most_distinct(nums, k - 1)

For [1, 2, 1, 2, 3] and K = 2:

12 − 5 = 7, which matches LeetCode's answer. Two passes, O(n) time, O(K) extra space.

Traps

• Guard negative limits. With K = 0, the second call is atMost(-1). No window, not even the empty one, has at most −1 distinct values. The shrink loop would never be satisfied and would run left past right. if k < 0: return 0 handles it.
• Counting needs the true while window. The if trick from Move 3 leaves [left..right] possibly invalid, and then right - left + 1 over-counts.
• Counts get big. n = 10⁵ allows n(n+1)/2 = 5,000,050,000 subarrays. Python integers don't overflow, but in Java or C++ that needs a 64-bit counter.

Your turn: LeetCode 1248: Count Number of Nice Subarrays. A subarray is nice if it contains exactly k odd numbers. Reduce it to something you've already built, then predict ([1, 1, 2, 1, 1], 3) and ([2, 2, 2, 1, 2, 2, 1, 2, 2, 2], 2).

def at_most_sum(nums, goal):
    if goal < 0:
        return 0              # no window of non-negative values sums to less than 0
    window = 0
    left = 0
    total = 0
    for right, x in enumerate(nums):
        window += x
        while window > goal:
            window -= nums[left]
            left += 1
        total += right - left + 1
    return total

def num_subarrays_with_sum(nums, goal):
    return at_most_sum(nums, goal) - at_most_sum(nums, goal - 1)

def number_of_nice_subarrays(nums, k):
    return num_subarrays_with_sum([x % 2 for x in nums], k)

When the window lies

Every variable window above rests on one fact: validity changes in one direction as the window grows or shrinks. Check it before you write the loop:

• Longest, at most, or counting: if [l..r] is valid, is [l+1..r] always valid? (shrink-closed)
• Shortest or at least: if [l..r] is valid, is [l..r+1] always valid? (extension-closed)

If the honest answer is "not always", the template still runs and still returns a number. It's just sometimes the wrong number.

Predict first: min_subarray_len(5, [1, -1, 5]) from Move 4. What does it return, and what is the true answer?

The same thing happens to the longest template. Take "longest subarray with sum ≤ 0" on [5, -10, 1]. The window starting at 0 is abandoned at right = 0 because [5] is invalid, so the template returns 2. But the whole array sums to −4, so the true answer is 3. Here, extending an invalid window made it valid.

Here is where each of these goes instead:

Note the first row. "Sum exactly k" fails as a single window even when every value is positive: [1, 1] sums to 2 but [1] doesn't. With non-negative values, Move 5's atMost subtraction rescues it. Negative values are what take that rescue away.

When you aren't sure, run the template against a brute-force reference on random small arrays that include negatives. The counterexamples above turn up within a few hundred tries.

Your turn: for each condition, run the one-sentence test and say which move applies, if any.

1. At most 3 zeros in the window.
2. Sum at most 10, with values between −5 and 5.
3. The window contains at least one vowel.
4. Product below k, with every value ≥ 1.

Final round: no label on the problem

Real problems don't say "sliding window". Find what is contiguous, pick the move, and check the direction test before writing the loop.

Challenge 1: cards from both ends

LeetCode 1423: Maximum Points You Can Obtain from Cards. Cards lie in a row. You take exactly k cards, each one from the left end or the right end, and score their total. For [1, 2, 3, 4, 5, 6, 1] with k = 3 the best is 12: take the three cards on the right, 5 + 6 + 1.

1. Your picks come from two ends, so nothing looks contiguous. What is contiguous here?
2. Which move applies, and with what window size?
3. Predict ([2, 2, 2], 2) and ([9, 7, 7, 9, 7, 7, 9], 7).

def max_score(card_points, k):
    n = len(card_points)
    keep = n - k                       # the cards you do NOT take form one contiguous block
    window = sum(card_points[:keep])
    smallest = window
    for right in range(keep, n):
        window += card_points[right] - card_points[right - keep]
        smallest = min(smallest, window)
    return sum(card_points) - smallest

Challenge 2: the baskets, revisited

Solve LeetCode 904: Fruit Into Baskets with code you have already written. Predict [1, 2, 3, 2, 2] and [3, 3, 3, 1, 2, 1, 1, 2, 3, 3, 4].

def total_fruit(fruits):
    return longest_at_most_k_distinct(fruits, 2)

Challenge 3: the one that isn't a window

Count the subarrays whose sum is exactly k. Values can be negative. Predict the answer for [1, -1, 1, -1] with k = 0, then say why no move from this lesson fits.

def subarray_sum_equals_k(nums, k):
    seen = {0: 1}             # prefix sum -> how many times it has occurred
    prefix = 0
    count = 0
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Cheat sheet

Before moving on, pick one of Fruit Into Baskets, Minimum Size Subarray Sum or Minimum Window Substring and rebuild it from a blank editor. Say out loud what the window state holds, which direction the condition closes in, why left never moves back, where the result is recorded and why there, and which input would break it. If you can do that for a longest problem, a shortest problem and a counting problem, you have the pattern rather than three memorised solutions.

Next: Maximum Subarray Sum for the case where a window fails and a running summary wins, Longest Substring Without Repeats for Move 3 in depth, and Hash Maps & Sets for prefix sums with a hash map.