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.
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How do you decide between a fixed-size and variable-size sliding window?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Fixed-size window: the problem explicitly specifies a window size K (e.g., “maximum sum of K consecutive elements,” “average of all subarrays of size K”). The window size never changes; right = left + K. Variable-size window: the problem asks for the longest/shortest subarray satisfying a condition (“longest subarray with sum <= K," "smallest window containing all characters of T"). The window expands right until a condition is violated, then contracts left until restored. Decision rule: if the problem gives you K (a fixed size), use fixed window. If the problem says "find the longest/shortest X such that condition Y holds," use variable window. Common variable window conditions: sum <= target, at most K distinct elements, character frequency covers all of T, difference between max and min <= limit. The condition must be "monotone" — adding elements only makes it easier (or harder) to satisfy, never flip-flops. If the condition is non-monotone (e.g., "exactly K distinct"), use the at-most-K trick: f(exactly K) = f(at most K) – f(at most K-1)."
}
},
{
"@type": "Question",
"name": "What is the monotonic deque and how does it apply to sliding window problems?",
"acceptedAnswer": {
"@type": "Answer",
"text": "A monotonic deque is a deque that maintains a monotonically increasing or decreasing sequence of values (by discarding elements that violate the monotone property). For sliding window maximum: maintain a decreasing deque of indices. When adding index i: pop from the back all indices j where nums[j] <= nums[i] (they can never be the maximum while i is in the window). Add i to the back. Pop from the front if the front index is outside the window. The front = maximum of the current window. Why it works: if nums[j] <= nums[i] and j = nums[j], so j is not the max) or has left the window. Either way, j will never be the window maximum again — safely discarded. Monotonic increasing deque: for sliding window minimum or shortest subarray with sum >= K (LC 862). Each element is added and removed from the deque at most once: O(n) total.”
}
},
{
“@type”: “Question”,
“name”: “How do you solve the “longest subarray with ones after deleting one element” (LC 1493)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “After deleting one element, the remaining subarray should have all 1s. Rephrase: find the longest window with at most one 0. Variable window: expand right, count zeros. When zero_count > 1: shrink left until zero_count == 1. Window length – 1 = length of subarray after deletion (we always delete one element, even if there’s no 0 — delete any 1). Track max window length, return max_window – 1. Edge case: if the entire array is all 1s, the answer is len(nums) – 1 (must delete one element). The “at most K zeros” pattern is a generalization of “at most K distinct” — the same variable window structure applies. Time O(n), space O(1). General pattern: “longest subarray with at most K of some condition violated” is always a variable window problem with a counter for violations.”
}
},
{
“@type”: “Question”,
“name”: “How do you solve the minimum size subarray sum problem (LC 209)?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Find the minimum length subarray with sum >= target. Variable window with a running sum: expand right, add nums[right] to window_sum. While window_sum >= target: record the window length, shrink left (subtract nums[left], increment left). The key: the while loop (not if) is essential — after finding a valid window, keep shrinking to find an even shorter valid window before moving right. O(n) time (each element added and removed at most once). Binary search alternative: compute prefix sums, then for each right index, binary search for the smallest left where prefix[right] – prefix[left] >= target. O(n log n) — worse. The sliding window is optimal here because the window sum is monotonically non-decreasing as right advances (all positive numbers). If the array could have negative numbers: the sum is no longer monotone, sliding window breaks, and a different approach (deque + prefix sums for LC 862) is needed.”
}
},
{
“@type”: “Question”,
“name”: “How does the “at most K” trick work for “exactly K” problems?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Some problems ask for subarrays with exactly K occurrences of something. Sliding window naturally handles “at most K” (expand until over K, then shrink). For “exactly K”: use the identity: count(exactly K) = count(at most K) – count(at most K-1). Both at-most-K and at-most-(K-1) use the same sliding window function with different K values. LC 992 (subarrays with exactly K different integers): count(at most K distinct) – count(at most K-1 distinct). LC 1248 (count number of nice subarrays with exactly K odd numbers): count(at most K odds) – count(at most K-1 odds). The trick works because: count(exactly K) = count(at most K) – count(subarrays with at most K-1) = count subarrays with K, K-1 occurrences minus those with K-1 or fewer = exactly K. This transforms a harder problem (exactly K, harder to maintain the invariant cleanly) into two easier problems (at most K, clean shrink condition). O(n) total, two passes through the array.”
}
}
]
}
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: Atlassian Interview Guide