Dashboard/Coding patterns/03. Sliding Window

CODING PATTERNS · LESSON 3 OF 28 · 68 MIN VIDEO · 24 PROBLEMS

Sliding Window

Module Progress (0 / 24 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (68 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Sliding Window — How the Pattern Works

The Sliding Window pattern maintains a contiguous range [left, right] over an array or string alongside an incremental aggregate state—such as a running sum or product, character frequency map, sliding hash set, or monotonic deque. Instead of recomputing aggregate properties from scratch across overlapping ranges, expanding right incorporates one incoming element and advancing left evicts one outgoing element in O(1) amortized time. Because both left and right advance monotonically without retreating, every index enters and leaves the window at most once, collapsing O(n * k) or O(n^2) brute-force range scans into O(n) time.

WHEN TO USE THIS PATTERN
  • Contiguous subarray or substring problems asking for the maximum/minimum length, optimal aggregate (sum, average, product), or count of valid contiguous runs.
  • Fixed-width window queries of a specified size k (e.g., rolling sums/averages, fixed-length substring deduplication, permutation/anagram matching, or nearby duplicates within distance k).
  • Dynamic-width monotonic constraints where adding elements on the right monotonically pushes a metric toward violation and removing elements on the left restores validity (e.g., positive-number sum/product caps, at most k distinct elements, or at most k flips/replacements).
  • Exact-cardinality or 'at least' subarray counting problems reducible via exact(k) = at_most(k) - at_most(k - 1) or complement prefix counting (total += left after shrinking to the boundary of invalidity).
COMMON INTERVIEW PITFALLS
  • Using dynamic sum/score shrinking when the array contains negative numbers: evicting a negative value increases the window sum, breaking the monotonicity required by two-pointer shrinking.
  • Initializing best = 0 when maximizing window sums or averages over potentially negative inputs; always seed best with the first valid window's aggregate or -math.inf.
  • Allowing left to move backward on stale index-map lookups (left = last[ch] + 1 without checking last[ch] >= left), or forgetting del count[x] when count[x] == 0 while relying on len(count).
  • Attempting to count exact-sum or exact-distinct subarrays with a single window when zeros or duplicate elements exist, instead of decomposing via at_most(k) - at_most(k - 1) (with at_most(< 0) = 0).
Fixed-Size Sliding WindowEvaluate every contiguous window of exact width k by adding index right and evicting index right - k in O(1) per step.
def fixed_window_max_sum(nums, k):
    window_sum = sum(nums[:k])
    best = window_sum
    for right in range(k, len(nums)):
        window_sum += nums[right] - nums[right - k]
        best = max(best, window_sum)
    return best
Dynamic Grow-and-Shrink WindowFind the longest contiguous range (or count valid ranges via right - left + 1) satisfying a monotonic window invariant.
def dynamic_window_longest(nums, k):
    count = {}
    left = best = 0
    for right, val in enumerate(nums):
        count[val] = count.get(val, 0) + 1
        while len(count) > k:
            count[nums[left]] -= 1
            if count[nums[left]] == 0:
                del count[nums[left]]
            left += 1
        best = max(best, right - left + 1)
    return best
Monotonic Deque Window ExtremaMaintain the exact maximum (or minimum) over a sliding window in O(1) amortized time per element.
from collections import deque
def sliding_window_max(nums, k):
    dq, result = deque(), []
    for right, val in enumerate(nums):
        while dq and nums[dq[-1]] <= val:
            dq.pop()
        dq.append(right)
        if dq[0] <= right - k:
            dq.popleft()
        if right >= k - 1:
            result.append(nums[dq[0]])
    return result
🔒 PRO PROBLEMTarget: O(n · m) time · O(1) space

03. Minimum Window Subsequence

Pattern Trigger: in order, gaps allowed → forward, then backward

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

A fixed window holds a thousand cells, and we keep its sum. It slides one step. How much work is the update?