Pattern 03 of 22
Sliding Window Pattern: Template + 116 LeetCode Problems
Collapse a nested loop over every subarray into a single pass with two indices.
- Easy
- 12
- Medium
- 74
- Hard
- 30
- Time
- O(n)
What the sliding window pattern is
A sliding window holds one contiguous stretch of the input between two indices, along with a running summary of what is inside it — a sum, a character count, a distinct-element count. Because the summary is updated incrementally as an index moves, advancing the window costs O(1) instead of re-reading it, which is what turns an O(n²) scan of every subarray into one linear pass. The right index always moves forward; the left index moves only while the window violates the constraint, so each element is added once and removed at most once. Two forms cover almost everything: a fixed window slides both ends in lockstep and answers questions about every subarray of length k, while a variable window grows greedily and shrinks from the left until it is legal again, answering questions about the longest or shortest subarray satisfying a condition.
When to use it
- The answer is a contiguous subarray or substring — not a subsequence, which cannot be described by two indices.
- You can update the window's summary in O(1) when an element enters or leaves it.
- The constraint is monotone: if a window is too long or too costly, extending it further cannot fix it.
- The brute force is two nested loops where the inner one recomputes work the outer one already did.
The sliding window template in Python
The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 116 problems listed below.
def longest_valid_window(nums):
left = 0
window = 0 # running summary of nums[left : right + 1]
best = 0
for right, value in enumerate(nums):
window += value # extend on the right
while window_is_illegal(window):
window -= nums[left] # shrink on the left until legal again
left += 1
best = max(best, right - left + 1)
return bestComplexity characteristics
- Time
- O(n)
- Auxiliary space
- O(1) to O(k)
Each index enters the window once and leaves it at most once, so the two pointers together travel at most 2n steps no matter how long any individual window gets — that is what makes a single pass equivalent to the O(n²) scan over every subarray. The space is whatever the running summary costs: O(1) for a sum or a counter, O(k) for a map of the elements currently inside the window, bounded by the alphabet rather than by the input length.
Eyes only
Meet the sliding window problem you did not practise.
In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.
All 116 sliding window LeetCode problems
Every problem in the library the sliding window pattern applies to, grouped by LeetCode's own difficulty rating. 102 of the 116 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.
Related LeetCode topics
Easy (12)
Medium (74)
Hard (30)
Sliding Window pattern FAQ
What is the sliding window pattern?
A sliding window holds one contiguous stretch of the input between two indices, along with a running summary of what is inside it — a sum, a character count, a distinct-element count.
How many LeetCode problems use the sliding window pattern?
This page lists 116 LeetCode problems that the sliding window pattern applies to: 12 Easy, 74 Medium and 30 Hard. 102 of them carry a complete Python solution with complexity analysis.
What is the time complexity of the sliding window pattern?
O(n) time and O(1) to O(k) space. Each index enters the window once and leaves it at most once, so the two pointers together travel at most 2n steps no matter how long any individual window gets — that is what makes a single pass equivalent to the O(n²) scan over every subarray. The space is whatever the running summary costs: O(1) for a sum or a counter, O(k) for a map of the elements currently inside the window, bounded by the alphabet rather than by the input length.
When should I use the sliding window pattern in an interview?
The answer is a contiguous subarray or substring — not a subsequence, which cannot be described by two indices. You can update the window's summary in O(1) when an element enters or leaves it.
Which sliding window problem should I start with?
LeetCode 219. Contains Duplicate II is the lowest-numbered Easy problem on this page, which makes it the usual starting point: the technique is visible without the problem's own complications getting in the way.
What patterns are related to sliding window?
Two Pointers, Prefix Sum, Hash Map, Monotonic Stack. Problems frequently sit in more than one of these, and the overlap is where the interesting follow-up questions come from.
More ways in: all 22 patterns, the curated study lists, or the full problem list.