Sliding Window Core Idea
Sliding window maintains a window [left, right] over a linear data structure (array, string). As the window expands (right advances) or contracts (left advances), we maintain a window state (sum, count, frequency map) without recomputing from scratch. O(n) instead of O(n^2) for naive nested loops. Two window types: fixed-size window (window size K is constant): right = left + K. Variable-size window: expand right until a condition is violated, then contract left until the condition is restored. Use when the problem asks for the longest/shortest subarray satisfying a condition.
Pattern 1: Longest Substring Without Repeating Characters (LC 3)
Expand right: add chars[right] to a frequency map. If any char count > 1 (violation): shrink left until the count is back to 1. Track max window length.
def length_of_longest_substring(s):
freq = {}
left = max_len = 0
for right, c in enumerate(s):
freq[c] = freq.get(c, 0) + 1
while freq[c] > 1:
freq[s[left]] -= 1
left += 1
max_len = max(max_len, right - left + 1)
return max_lenPattern 2: At Most K Distinct Characters (LC 340, 904)
Longest substring with at most K distinct characters. Expand right, add to freq map. When len(freq) > K (violation): shrink left until len(freq) == K. The “exactly K” variant: f(exactly K) = f(at most K) – f(at most K-1). This “at most K → exactly K” trick appears often.
def longest_k_distinct(s, k):
freq = {}
left = res = 0
for right, c in enumerate(s):
freq[c] = freq.get(c, 0) + 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
res = max(res, right - left + 1)
return resPattern 3: Minimum Window Substring (LC 76)
Find the smallest window in s containing all characters of t. Maintain a “need” counter (how many characters still needed). Expand right. When need == 0 (window is valid): record the window, shrink left. When left’s character is needed: increment need. Continue expanding right. O(n + m) time.
from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
left = res_l = res_r = 0
res_len = float('inf')
for right, c in enumerate(s):
if need[c] > 0:
missing -= 1
need[c] -= 1
if missing == 0:
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if right - left + 1 < res_len:
res_len = right - left + 1
res_l, res_r = left, right + 1
need[s[left]] += 1
missing += 1
left += 1
return s[res_l:res_r] if res_len < float('inf') else ''Pattern 4: Sliding Window Maximum (LC 239)
Find the maximum in every window of size K. Naive: O(nK). Optimal with monotonic deque: O(n). Maintain a deque of indices in decreasing order of values (monotonic decreasing). For each new element: remove from the right all indices with values <= current value (they can never be the maximum). Add current index to the right. Remove from the left if the front index is out of the current window. The front of the deque = maximum of the current window.
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
res = []
for i, n in enumerate(nums):
while dq and nums[dq[-1]] = k - 1:
res.append(nums[dq[0]])
return resThe monotonic deque pattern appears in: LC 239 (max), LC 1438 (max – min = K). When you need min/max over a sliding window: think monotonic deque.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide