The Sliding Window Technique
The sliding window technique optimizes brute-force O(n^2) or O(n^3) problems to O(n) by maintaining a window (subarray or substring) that expands and contracts as we scan left to right. Instead of recomputing the answer for every possible window from scratch, we update incrementally as elements enter and leave the window. Sliding window applies to problems involving: contiguous subarrays or substrings, a condition that must be satisfied within the window, and a min/max/count query on the window.
Template 1: Fixed-Size Window
When the window size K is fixed, initialize the first window then slide right, adding the incoming element and removing the outgoing element.
# Maximum sum of subarray of size K
def max_sum_fixed(nums: list, k: int) -> int:
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # slide: add right, remove left
max_sum = max(max_sum, window_sum)
return max_sum
# Average of all subarrays of size K
def find_averages(nums, k):
result = []
window_sum = sum(nums[:k])
result.append(window_sum / k)
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k]
result.append(window_sum / k)
return result
Template 2: Variable-Size Window (Expand/Contract)
When the window size is variable, use a left and right pointer. Expand right unconditionally; contract left when the window violates the constraint. Track the answer at each valid state.
# Longest subarray with sum int:
left = window_sum = max_len = 0
for right in range(len(nums)):
window_sum += nums[right]
while window_sum > target: # contract until valid
window_sum -= nums[left]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
# Minimum size subarray with sum >= target
def min_subarray_sum(target: int, nums: list) -> int:
left = window_sum = 0
min_len = float("inf")
for right in range(len(nums)):
window_sum += nums[right]
while window_sum >= target:
min_len = min(min_len, right - left + 1)
window_sum -= nums[left]
left += 1
return min_len if min_len != float("inf") else 0
Template 3: String Window with Character Counts
String sliding window problems track character frequencies within the window using a hash map or array of size 26.
# Longest substring without repeating characters
def length_of_longest_substring(s: str) -> int:
char_index = {}
left = max_len = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1 # jump left past duplicate
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
# Minimum window substring: smallest window in s containing all chars of t
def min_window_substring(s: str, t: str) -> str:
need = {}
for c in t: need[c] = need.get(c, 0) + 1
have, total = 0, len(need)
window = {}
left = 0
result = (-1, -1)
min_len = float("inf")
for right, char in enumerate(s):
window[char] = window.get(char, 0) + 1
if char in need and window[char] == need[char]:
have += 1
while have == total:
if right - left + 1 < min_len:
min_len = right - left + 1
result = (left, right)
window[s[left]] -= 1
if s[left] in need and window[s[left]] < need[s[left]]:
have -= 1
left += 1
l, r = result
return s[l:r+1] if min_len != float("inf") else ""
Template 4: Deque-Based Sliding Window Maximum
Finding the maximum (or minimum) in every window of size K requires a monotonic deque that maintains candidates in decreasing order. Elements are removed from the back when a larger element arrives (they can never be the window maximum), and from the front when they fall out of the window.
from collections import deque
def sliding_window_maximum(nums: list, k: int) -> list:
dq = deque() # stores indices, values in dq are decreasing
result = []
for i, num in enumerate(nums):
# Remove elements outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back (they cannot be maximum)
while dq and nums[dq[-1]] = k - 1:
result.append(nums[dq[0]]) # front is always the max
return result
# Time: O(n), Space: O(k)
Common Sliding Window Problems
- Fixed window: Maximum Sum Subarray of Size K, Find All Anagrams in a String, Permutation in String
- Variable window: Longest Substring Without Repeating Characters, Longest Subarray with Ones after Replacement, Fruit Into Baskets
- String window: Minimum Window Substring, Longest Substring with At Most K Distinct Characters
- Deque window: Sliding Window Maximum, Jump Game VI, Longest Subarray with Absolute Diff at Most Limit
How to Recognize Sliding Window Problems
- Problem involves a contiguous subarray or substring (not arbitrary subsets)
- You need min, max, sum, count, or a condition within the window
- Brute force has a nested loop — two loops over the same array
- The window property is monotone: once the window becomes invalid, adding more elements from the left will not fix it (only shrinking from left will)
Frequently Asked Questions
When should you use the sliding window technique?
Use sliding window when: (1) the problem asks about a contiguous subarray or substring — not arbitrary subsets; (2) you need to find a minimum, maximum, count, or condition within that window; and (3) the brute force solution uses a nested loop over the same array (O(n^2)). The key insight is that the window property must be monotone: adding elements to the window can only make it more or less valid in one direction, never oscillate. This lets you expand and contract with two pointers without missing any valid window. If adding elements can both improve and worsen the condition (e.g., absolute value constraints), sliding window does not directly apply and you may need a deque or segment tree.
What is the difference between fixed-size and variable-size sliding windows?
Fixed-size sliding window: the window size K is given. Initialize the first window of size K, then slide right one step at a time — add the new right element, remove the leftmost element, update the answer. Time O(n). Examples: maximum sum of K consecutive elements, find all anagrams of a pattern in a string (fixed window = len(pattern)). Variable-size sliding window: the window size is determined by a constraint. Use two pointers (left and right). Expand right unconditionally; when the window violates the constraint, contract from the left. The answer is updated at each valid state (either at every right position, or when contracting). Time O(n) because each element is added and removed at most once. Examples: longest substring without repeating characters, minimum window substring, longest subarray with sum less than or equal to target.
How does a monotonic deque improve sliding window maximum to O(n)?
Naively finding the maximum in every window of size K takes O(n*K) — scan each window entirely. A monotonic deque reduces this to O(n). The deque stores indices of elements in decreasing order of value. Invariants: (1) the deque front is always the index of the current window maximum; (2) the deque never contains an element that is smaller than a more recently added element (those can never be the maximum). When adding element i: remove from the back all indices whose values are less than nums[i] — they will never be the window maximum because i is newer and larger; then add i to the back. When the front index falls out of the window (i – dq[0] >= k), remove it from the front. Each element is pushed and popped at most once, giving O(n) total operations.
{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “@type”: “Question”, “name”: “When should you use the sliding window technique?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Use sliding window when: (1) the problem asks about a contiguous subarray or substring — not arbitrary subsets; (2) you need to find a minimum, maximum, count, or condition within that window; and (3) the brute force solution uses a nested loop over the same array (O(n^2)). The key insight is that the window property must be monotone: adding elements to the window can only make it more or less valid in one direction, never oscillate. This lets you expand and contract with two pointers without missing any valid window. If adding elements can both improve and worsen the condition (e.g., absolute value constraints), sliding window does not directly apply and you may need a deque or segment tree.” } }, { “@type”: “Question”, “name”: “What is the difference between fixed-size and variable-size sliding windows?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Fixed-size sliding window: the window size K is given. Initialize the first window of size K, then slide right one step at a time — add the new right element, remove the leftmost element, update the answer. Time O(n). Examples: maximum sum of K consecutive elements, find all anagrams of a pattern in a string (fixed window = len(pattern)). Variable-size sliding window: the window size is determined by a constraint. Use two pointers (left and right). Expand right unconditionally; when the window violates the constraint, contract from the left. The answer is updated at each valid state (either at every right position, or when contracting). Time O(n) because each element is added and removed at most once. Examples: longest substring without repeating characters, minimum window substring, longest subarray with sum less than or equal to target.” } }, { “@type”: “Question”, “name”: “How does a monotonic deque improve sliding window maximum to O(n)?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Naively finding the maximum in every window of size K takes O(n*K) — scan each window entirely. A monotonic deque reduces this to O(n). The deque stores indices of elements in decreasing order of value. Invariants: (1) the deque front is always the index of the current window maximum; (2) the deque never contains an element that is smaller than a more recently added element (those can never be the maximum). When adding element i: remove from the back all indices whose values are less than nums[i] — they will never be the window maximum because i is newer and larger; then add i to the back. When the front index falls out of the window (i – dq[0] >= k), remove it from the front. Each element is pushed and popped at most once, giving O(n) total operations.” } } ] }