Sliding Window

Expand-shrink template for longest/shortest substring or subarray with property.

sliding-window.mdreadme

03 — Sliding Window

Neetcode Week 2b. Sliding window is a same-direction-pointer specialization for "longest/shortest substring/subarray with property P". When you spot the trigger, you should reach for this template within seconds.

Table of Contents

  1. The intuition
  2. Fixed-size window template
  3. Variable-size window template
  4. The expand-shrink rule
  5. Walked-through problems
  6. Counter-based windows for substring matching
  7. Monotonic-deque windows
  8. Pitfalls
  9. Practice list

1. The intuition

You want to consider every contiguous subarray (or substring) of nums. There are O(n²) of them, so a naive enumeration is O(n²) and revisits work.

Sliding window maintains a "window" [l, r] where the property might hold, and advances r (expand) or l (shrink) one step at a time. Each pointer moves only forward, so total moves ≤ 2n → O(n).

nums = [a, b, c, a, b, c, b, b]
        l-r                          window = "a"     ← expand
        l    r                       window = "ab"    ← expand
        l       r                    window = "abc"   ← expand
        l          r                 window = "abca"  ← duplicate! shrink
           l       r                 window = "bca"   ← l moved past first 'a'

Each character is added once when r advances and removed once when l advances. Total work O(n).

2. Fixed-size window template

Use when the problem says "window of size k" explicitly.

def fixed_window(arr, k):
    if k > len(arr): return None
    
    # Build initial window [0..k-1]
    window = sum(arr[:k])
    best = window
    
    # Slide: add arr[r], drop arr[l]
    for r in range(k, len(arr)):
        window += arr[r] - arr[r - k]   # add new, remove old
        best = max(best, window)
    
    return best

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

Initial window [0,1,2]: 2+1+5 = 8 → best=8
r=3: window = 8 + 1 - 2 = 7;  best=8
r=4: window = 7 + 3 - 1 = 9;  best=9
r=5: window = 9 + 2 - 5 = 6;  best=9
return 9

Generic template (any aggregation)

def fixed_window_generic(arr, k):
    win = collections.Counter(arr[:k])    # or any state
    best = process(win)
    for r in range(k, len(arr)):
        win[arr[r]] += 1                  # add right
        win[arr[r-k]] -= 1                # remove left
        if win[arr[r-k]] == 0:
            del win[arr[r-k]]
        best = max(best, process(win))
    return best

3. Variable-size window template

Use when window size depends on a property (the most common case).

def variable_window(arr):
    l = 0
    state = init_state()
    best = 0
    for r in range(len(arr)):
        # 1. Add arr[r] to window
        update_state_add(state, arr[r])
        
        # 2. Shrink from left while window is invalid
        while not valid(state):
            update_state_remove(state, arr[l])
            l += 1
        
        # 3. Update answer
        best = max(best, r - l + 1)
    return best

The pattern: expand until invalid, shrink until valid, record best.

Variant — find shortest window satisfying P

Sometimes you want the smallest window where P holds (not the largest where it doesn't). Tweaks:

def shortest_window(arr):
    l = 0
    state = init_state()
    best = float('inf')
    for r in range(len(arr)):
        update_state_add(state, arr[r])
        # Shrink while STILL valid (we want minimum)
        while valid(state):
            best = min(best, r - l + 1)
            update_state_remove(state, arr[l])
            l += 1
    return best if best != float('inf') else 0

Notice the difference: in the longest-with-no-bad-property case we shrink while invalid; in the shortest-satisfying case we shrink while still valid.

4. The expand-shrink rule

The right rules for r += 1 (expand) and l += 1 (shrink) come from the property:

Property typeExpand onShrink while
"longest substring with at most k distinct"always (each iter)distinct > k
"longest substring without repeating chars"alwaysduplicate of arr[r] in window
"shortest subarray with sum >= s"alwayswindow-sum >= s (record before shrinking)
"longest with sum <= s"alwayswindow-sum > s

Mental model: r is the unconditional driver (advances every iteration). l is the conditional follower (advances inside a while to restore an invariant).

5. Walked-through problems

Best Time to Buy and Sell Stock (Easy) — minimum-tracking variant

Single pass: pick a buy day and a later sell day for max profit.

This is technically not a sliding window but uses the same idea of maintaining state as a single pointer advances:

def max_profit(prices):
    min_so_far = float('inf')
    best = 0
    for p in prices:
        if p < min_so_far:
            min_so_far = p
        else:
            best = max(best, p - min_so_far)
    return best

Longest Substring Without Repeating Characters (Medium)

"abcabcbb" → 3 ("abc")

def length_of_longest_substring(s):
    seen = {}                    # char → most recent index
    l = 0
    best = 0
    for r, c in enumerate(s):
        if c in seen and seen[c] >= l:
            l = seen[c] + 1      # skip past previous occurrence
        seen[c] = r
        best = max(best, r - l + 1)
    return best

Why two conditions (c in seen and seen[c] >= l)? seen may carry stale entries from before the current window. Only act on duplicates that are still inside the window.

Trace "abcabcbb":

r=0 a: seen={a:0}, l=0, best=1 ("a")
r=1 b: seen={a:0,b:1}, l=0, best=2 ("ab")
r=2 c: seen={a:0,b:1,c:2}, l=0, best=3 ("abc")
r=3 a: a in seen, seen[a]=0 >= l=0 → l=1; seen[a]=3, best=3
r=4 b: b in seen, seen[b]=1 >= l=1 → l=2; seen[b]=4, best=3
r=5 c: c in seen, seen[c]=2 >= l=2 → l=3; seen[c]=5, best=3
r=6 b: b in seen, seen[b]=4 >= l=3 → l=5; seen[b]=6, best=3
r=7 b: b in seen, seen[b]=6 >= l=5 → l=7; seen[b]=7, best=3
return 3

Longest Repeating Character Replacement (Medium)

Given a string and integer k, you can replace any k characters. Find the longest substring with all same character after at most k replacements.

Insight: a window is valid iff window_length - count_of_most_frequent_char <= k.

def character_replacement(s, k):
    count = {}
    l = 0
    max_freq = 0
    best = 0
    for r in range(len(s)):
        count[s[r]] = count.get(s[r], 0) + 1
        max_freq = max(max_freq, count[s[r]])
        
        # Window invalid if (length - max_freq) > k → too many replacements needed
        while (r - l + 1) - max_freq > k:
            count[s[l]] -= 1
            l += 1
            # NOTE: max_freq might be stale here, but we never decrease it.
            #       This is OK because best only grows when we have a *better* max_freq.
        
        best = max(best, r - l + 1)
    return best

Subtle invariant: we never recompute max_freq when shrinking, even though it might be stale (over-estimated). Because the window length only updates best when we expand, and best is r - l + 1, a stale max_freq just means we shrink less aggressively than strictly needed — but we never report a wrong best, since best is computed from indices, not from the (possibly stale) max_freq. This is the elegant trick that makes the algorithm O(n) instead of O(n × 26).

Minimum Window Substring (Hard)

Find the smallest window in s containing all chars of t (with multiplicities).

from collections import Counter

def min_window(s, t):
    if not t or not s: return ""
    
    need = Counter(t)              # what we need
    have = {}                      # what we have in window
    have_count = 0                 # number of distinct chars satisfied
    need_count = len(need)
    
    l = 0
    best = (-1, 0, 0)              # (length, l, r); -1 = not found
    
    for r in range(len(s)):
        c = s[r]
        have[c] = have.get(c, 0) + 1
        if c in need and have[c] == need[c]:
            have_count += 1
        
        while have_count == need_count:
            if best[0] == -1 or (r - l + 1) < best[0]:
                best = (r - l + 1, l, r)
            
            # Shrink from left
            have[s[l]] -= 1
            if s[l] in need and have[s[l]] < need[s[l]]:
                have_count -= 1
            l += 1
    
    return s[best[1] : best[2] + 1] if best[0] != -1 else ""

Why have_count not have == need: Comparing two dicts each iteration would be O(26) per step = O(26n). have_count tracks satisfied keys in O(1), making the algorithm O(n).

Trace concept: have_count increments when a char's count first reaches its needed count. Decrements when shrinking drops it below needed count.

Sliding Window Maximum (Hard) — see §7

6. Counter-based windows

For substring matching ("permutation in string", "find all anagrams"), use a fixed-size window with character counts:

def find_anagrams(s, p):
    if len(p) > len(s): return []
    
    p_count = [0] * 26
    s_count = [0] * 26
    for c in p:
        p_count[ord(c) - ord('a')] += 1
    
    res = []
    for i in range(len(s)):
        s_count[ord(s[i]) - ord('a')] += 1     # add right
        if i >= len(p):
            s_count[ord(s[i - len(p)]) - ord('a')] -= 1   # remove left
        if s_count == p_count:
            res.append(i - len(p) + 1)
    return res

Subtle: comparing two length-26 lists is O(26) = O(1) constant work. So this is O(n).

7. Monotonic-deque windows

Trigger: "sliding window maximum/minimum" of size k.

A naive O(n·k) — recompute max each window. We can do O(n) with a deque storing indices, in decreasing order of value.

Sliding Window Maximum (Hard)

from collections import deque

def max_sliding_window(nums, k):
    q = deque()                            # indices, vals decreasing
    res = []
    for i, x in enumerate(nums):
        # 1. Pop indices out of the window from front
        while q and q[0] <= i - k:
            q.popleft()
        # 2. Pop smaller values from back (they can never be the max while x is around)
        while q and nums[q[-1]] < x:
            q.pop()
        # 3. Push this index
        q.append(i)
        # 4. Record max once first window is built
        if i >= k - 1:
            res.append(nums[q[0]])
    return res

Why O(n)? Each index is pushed once and popped at most once across the whole run. Total deque operations ≤ 2n.

Why "decreasing values"? The front is always the max of the current window. Smaller values popped from the back are dominated forever (they're older AND smaller).

ASCII trace for nums = [1,3,-1,-3,5,3,6,7], k = 3:

i=0 (1):  q=[0]              → window not full
i=1 (3):  pop 0 (1<3). q=[1] → window not full
i=2 (-1): q=[1,2]            → window full, max=nums[1]=3
i=3 (-3): pop 1 (i-k=0). q=[2,3] (3 stays as -1<−3 false, wait -1>-3 so don't pop 2)
   Actually: pop front while q[0] ≤ i-k=0 → pop 1. Then q=[2]; push -3 → q=[2,3]. max=nums[2]=-1
i=4 (5):  pop -3<5, pop -1<5 → q=[]; push 4 → q=[4]. max=5
i=5 (3):  3<5 keep. q=[4,5]. max=5
i=6 (6):  pop 3<6, pop 5<6 → q=[]; push 6 → q=[6]. max=6
i=7 (7):  pop 6<7 → q=[]; push 7 → q=[7]. max=7

result = [3, 3, 5, 5, 6, 7]

This monotonic deque technique appears in many problems beyond sliding window — see 04-stack.md.

8. Pitfalls

Forgetting to update best inside vs outside the inner while

For the longest pattern, update best after shrinking (window is now valid):

while invalid: l += 1
best = max(best, r - l + 1)

For the shortest pattern, update best before shrinking (we still satisfy P):

while valid:
    best = min(best, r - l + 1)
    l += 1

Stale state in dict-tracking

When shrinking, decrement counts. Either:

  • Delete key when count hits 0: if count[c] == 0: del count[c]
  • Or use count[c] > 0 guards in lookups.

Initial-window edge case

For fixed-size, handle len(arr) < k upfront. For variable-size, ensure the loop body works on a 1-element window.

Misidentifying fixed vs variable

If the problem says "find longest contiguous substring with at most k distinct chars," that's variable, not fixed-size-k. Fixed = "window size is exactly k."

9. Practice list

#ProblemTypeDifficulty
121Best Time to Buy and Sell StockTracking minEasy
3Longest Substring Without Repeating CharsVariableMedium
424Longest Repeating Character ReplacementVariable + max_freq trickMedium
567Permutation in StringFixed + counterMedium
438Find All Anagrams in a StringFixed + counterMedium
76Minimum Window SubstringVariable shortestHard
239Sliding Window MaximumMonotonic dequeHard
209Minimum Size Subarray SumVariable shortestMedium
904Fruit Into BasketsVariable, ≤2 distinctMedium
1004Max Consecutive Ones IIIVariable, k zerosMedium

TL;DR ✅

  • Fixed window: size given. Initialize, then slide one step adding right and removing left.
  • Variable window: expand r always, shrink l while invariant breaks.
  • Longest-where-property-holds: shrink while invalid, update best after.
  • Shortest-where-property-holds: shrink while valid, update best before shrink.
  • Counter-based windows match anagrams with O(1) constant-time comparisons.
  • Monotonic deque does sliding max/min in O(n) by storing decreasing-value indices.
  • Total complexity O(n) because each pointer advances at most n times.

Next: 04-stack.md.

External resources

problems/6 entries
●main
UTF-8·typescript