The Universal Window Template

One skeleton that solves the entire family — when to use fixed vs dynamic, and how to adapt the shrink condition.

6 min readLeetCode Patterns for InterviewsCode

The Template

Universal sliding window skeleton


# FIXED window (size k):
def fixed_window(nums, k):
    window = nums[:k]           # build first window
    result = process(window)    # measure first window
    for i in range(k, len(nums)):
        window.pop(0)           # remove leftmost
        window.append(nums[i])  # add rightmost
        result = combine(result, process(window))
    return result

# DYNAMIC window (maximize valid):
def max_valid_window(nums, constraint):
    l, best = 0, 0
    for r in range(len(nums)):
        add(nums[r])            # expand right
        while not valid():      # shrink while invalid
            remove(nums[l])
            l += 1
        best = max(best, r - l + 1)  # window is valid
    return best

# DYNAMIC window (minimize covering):
def min_covering_window(s, t):
    need = build_need(t)
    l, best = 0, float('inf')
    formed = 0
    for r in range(len(s)):
        add(s[r])               # expand right
        if satisfies(s[r]):
            formed += 1
        while formed == len(need):  # window covers all
            best = min(best, r - l + 1)
            remove(s[l])
            l += 1
    return best

The key decision: do you measure AFTER ensuring validity (maximize valid window) or BEFORE trying to shrink (minimize valid window)?

Variants

Problem type	Template	Classic examples
Max subarray/substring satisfying constraint	Dynamic, measure after valid check	Longest substr w/o repeats, max vowels
Min subarray/substring covering requirement	Dynamic, measure inside valid loop then shrink	Min window substring, smallest covering window
All windows of fixed size k	Fixed, slide by 1 each step	Max avg subarray, permutation in string
Count windows with exactly k distinct	Two dynamic windows: 'at most k' minus 'at most k-1'	Subarrays with k distinct integers

Decision Tree

How to choose your template

Ask yourself: (1) Is the window size fixed? If yes → fixed window. (2) Am I maximizing or minimizing? Maximize → measure after valid check. Minimize → measure inside valid loop. (3) What is the shrink condition? This tells you what to track in the window.

Fixed window: window size k is given, slide and compute each window
Dynamic maximize: expand right, shrink only when invalid, measure after each valid state
Dynamic minimize: expand right, measure when valid, shrink to find smallest valid window
Count of exactly k: use (at most k) - (at most k-1) identity, two dynamic windows

Exactly K distinct — using the at-most trick


def subarrays_with_k_distinct(nums: list[int], k: int) -> int:
    """Count subarrays with exactly k distinct integers.
    
    Key insight: exactly(k) = at_most(k) - at_most(k-1)
    """
    def at_most(k: int) -> int:
        freq = {}
        l, count = 0, 0
        for r in range(len(nums)):
            freq[nums[r]] = freq.get(nums[r], 0) + 1
            while len(freq) > k:
                freq[nums[l]] -= 1
                if freq[nums[l]] == 0:
                    del freq[nums[l]]
                l += 1
            count += r - l + 1  # all windows ending at r
        return count

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

# Usage
print(subarrays_with_k_distinct([1, 2, 1, 2, 3], 2))  # 7

The at-most(k) function counts all subarrays with at most k distinct. The difference gives exactly k. This avoids the tricky 'exactly k' shrink logic.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.

Stage 1 · Code

Two Pointers & Sliding Window