Pattern 1 of 27
Sliding Window
Keep a contiguous window over an array or string and move its edges instead of re-scanning every subarray.
- Cost
- O(n) time, O(k) space for the window summary
- Problems
- 6
When to reach for it
- The answer is a contiguous subarray or substring.
- The prompt asks for the longest, the shortest, or a count of windows that satisfy a rule.
- Growing the window can only break the rule, and shrinking it can only repair it.
How it works
A brute force checks every start and every end, which is O(n²) windows. A sliding window notices that when the right edge moves one step, almost all of the previous window's work is still valid. Extend right to take in a new element, update a small summary of the window such as a count map or a sum, and while the window breaks the rule, advance left and undo that element. Each index enters and leaves once, so the whole scan is linear. The real design decision is choosing a summary that answers "is this window valid" in constant time.
The template
Written for Longest Substring Without Repeating Characters (write-up)
def length_of_longest_substring(s):
count = {}
left = best = 0
for right, ch in enumerate(s):
count[ch] = count.get(ch, 0) + 1
while count[ch] > 1: # the window broke the rule: shrink it
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return bestSix problems, in learning order
- 1.Longest Substring Without Repeating CharactersLeetCode 3Shrink whenever the new character already appears in the window.Medium
- 2.Minimum Window SubstringLeetCode 76Minimum window: shrink while the window still covers every required count.Hard
- 3.Minimum Size Subarray SumLeetCode 209Positive numbers only, which is why shrinking once the sum reaches the target is safe.Medium
- 4.Longest Repeating Character ReplacementLeetCode 424The window stays valid while its length minus its top letter count is at most k.Medium
- 5.Permutation in StringLeetCode 567Fixed-size window: compare its letter counts with the pattern's.Medium
- 6.Fruit Into BasketsLeetCode 904Longest window holding at most two distinct values.Medium
What usually goes wrong
- Using if instead of while when shrinking: one step left may not restore the rule.
- Updating the answer before the window is valid again, which counts broken windows.
- Negative numbers break sum-based windows because shrinking no longer lowers the sum. Prefix sums handle those.
Sliding Window, answered
When should I use the sliding window pattern?
The answer is a contiguous subarray or substring. The prompt asks for the longest, the shortest, or a count of windows that satisfy a rule. Growing the window can only break the rule, and shrinking it can only repair it.
What is the time complexity of sliding window?
O(n) time, O(k) space for the window summary. The real design decision is choosing a summary that answers "is this window valid" in constant time.
Which problem should I start with for sliding window?
Start with Longest Substring Without Repeating Characters (LeetCode 3, Medium). Shrink whenever the new character already appears in the window. The six problems on this page are in learning order.