Turn nested scans of subarrays and substrings into one linear pass by maintaining a window that grows and shrinks as you go.
What the sliding window pattern is
A sliding window is a contiguous range over an array or string that you move forward one element at a time, updating a running answer instead of recomputing it from scratch. The naive way to examine every subarray is two nested loops - O(n²) or worse. The window observation is that when the range shifts right by one, almost everything inside it stays the same: one element enters, and possibly some leave. If you can update your bookkeeping for just those elements in O(1), the whole scan collapses to O(n).
The pattern comes in two flavors. A fixed-size window slides a range of exactly k elements and asks something about each position - the classic 'maximum sum of any k consecutive elements'. A variable-size window grows the right edge every step and shrinks the left edge only when some constraint breaks - 'longest substring without repeating characters' is the canonical example. Fixed windows are about updating a value; variable windows are about maintaining an invariant.
How to recognize it
Reach for a sliding window when all three of these hold: the input is a linear sequence (array or string), the question is about a contiguous run of it (subarray or substring - not subsequence), and the quantity you are tracking can be updated incrementally when one element enters or leaves. Phrases like 'longest substring such that…', 'shortest subarray with…', 'maximum sum of k consecutive…', or 'contains at most k distinct…' are strong signals.
The classic trap is applying a window where the incremental-update property fails. If elements can be negative, 'subarray sum ≥ target' loses the monotonicity that makes shrinking correct - growing the window no longer strictly increases the sum, so the shrink decision becomes meaningless. And if the problem says subsequence (non-contiguous), a window is the wrong shape entirely.
The variable-window template
Nearly every variable-window problem fits one skeleton: expand right unconditionally, then shrink left while the window is invalid, then record the answer. The invariant to internalize: after the inner while-loop finishes, the window is always valid, so it is always safe to record it.
pseudocode
left = 0
state = empty # counts, sum - whatever the constraint needs
for right in 0 .. n-1:
add a[right] to state # window grows
while state violates the constraint:
remove a[left] from state # window shrinks
left += 1
answer = best(answer, window [left, right])
Complexity
Time is O(n) even though there is a loop inside a loop: `left` only ever moves forward, so across the entire run each element is added once and removed at most once - 2n pointer movements total, not n². Space is whatever the window state costs: O(1) for a running sum, O(k) or O(alphabet) for a frequency map.
Common pitfalls
Shrinking with an `if` instead of a `while` - one new element can invalidate the window by more than one step, so a single removal is not enough.
Recording the answer before the window is valid again. For 'longest valid window' problems, record after the shrink loop; for 'shortest window satisfying X' problems, the roles flip - you shrink while the window is still valid, recording as you go.
Off-by-one on window length: the window [left, right] inclusive has length right − left + 1. Write that expression once and reuse it.
Forgetting to clean up state when the left element leaves - decrement the count and delete the key when it hits zero, or your 'distinct characters' check quietly rots.
Worked examples
1. Maximum sum of k consecutive elementseasy
Given an array of integers and a number k, return the maximum sum of any k consecutive elements.
Brute force computes the sum of each of the n−k+1 ranges in O(k) each - O(nk) total. Notice how much work repeats: adjacent ranges share k−1 elements.
When the window slides right by one, its sum changes by exactly (entering element) − (leaving element). That is an O(1) update.
Build the first window's sum in O(k), then slide: add a[i], subtract a[i−k], compare against the best so far.
The answer is the maximum seen. One pass, O(n) time, O(1) space.
pseudocode
windowSum = sum(a[0..k-1])
best = windowSum
for i in k .. n-1:
windowSum += a[i] - a[i-k]
best = max(best, windowSum)
return best
Remember: A fixed window never recomputes - it repairs: one element in, one element out, O(1) per slide.
2. Longest substring without repeating charactersmedium
Given a string, return the length of the longest substring that contains no repeated characters.
The constraint is 'all characters in the window are distinct'. A frequency map (or last-seen index map) can tell us in O(1) whether the entering character breaks it.
Expand right one character at a time. When s[right] is already in the window, the window is invalid - shrink from the left, removing characters from the map, until the duplicate occurrence is gone.
After the shrink loop the window is valid again, so right − left + 1 is a candidate answer.
Each character enters once and leaves at most once, so the total work is O(n) despite the nested loop.
pseudocode
left = 0, best = 0
counts = empty map
for right in 0 .. n-1:
counts[s[right]] += 1
while counts[s[right]] > 1:
counts[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best
Remember: The while-loop restores the invariant 'window is valid'; the answer is only ever recorded when the invariant holds.
3. Longest substring with at most k distinct charactersmedium
Given a string and an integer k, return the length of the longest substring containing at most k distinct characters.
Same skeleton as the previous problem - only the validity test changes: 'the frequency map has at most k keys'.
Expand right, incrementing the entering character's count. If the map now has k+1 distinct keys, shrink from the left.
When a count reaches zero during shrinking, delete the key - the map's size is the distinct-character count, and stale zero-count keys would corrupt it.
Record right − left + 1 after each shrink. This 'swap the invariant, keep the template' move is exactly what makes the pattern reusable across dozens of problems.
pseudocode
left = 0, best = 0
counts = empty map
for right in 0 .. n-1:
counts[s[right]] += 1
while size(counts) > k:
counts[s[left]] -= 1
if counts[s[left]] == 0: delete counts[s[left]]
left += 1
best = max(best, right - left + 1)
return best
Remember: Variable-window problems differ only in their invariant - learn the template once, swap the validity test per problem.
4. Minimum size subarray with sum at least targetmedium
Given an array of positive integers and a target, return the length of the shortest contiguous subarray whose sum is at least the target (0 if none exists).
This is the 'shortest valid window' variant, so the shrink logic inverts: we shrink while the window is still valid, because a shorter valid window is a better answer.
Expand right, adding to a running sum. Whenever the sum reaches the target, record the current length, then remove a[left] and keep shrinking as long as validity survives.
Positivity of the elements is what makes this correct: growing the window can only increase the sum, shrinking can only decrease it. With negative numbers this monotonicity dies and the pattern silently gives wrong answers - that variant needs prefix sums instead.
O(n) time, O(1) space, same two-pointer accounting as always.
pseudocode
left = 0, sum = 0, best = infinity
for right in 0 .. n-1:
sum += a[right]
while sum >= target:
best = min(best, right - left + 1)
sum -= a[left]
left += 1
return best == infinity ? 0 : best
Remember: 'Longest valid' records after restoring validity; 'shortest valid' records while validity still holds - same template, mirrored.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1Why is the variable-size sliding window O(n) despite having a while-loop inside a for-loop?
Because the while-loop runs at most a constant number of times per iteration
✓ Because left only moves forward, so each element is added once and removed at most once across the whole run
Because the inner loop only runs when the input is already sorted
It isn't - the worst case is O(n²)
Amortized analysis: the total number of left-pointer movements across the entire run is at most n, so the combined work of all inner-loop iterations is O(n), giving 2n total pointer steps.
2Which problem statement is NOT a sliding-window candidate?
Longest substring with at most 2 distinct characters
Maximum sum of any 5 consecutive elements
✓ Longest increasing subsequence of an array
Shortest subarray of positive integers with sum ≥ 100
A subsequence is not contiguous - elements can be skipped - so there is no 'window' to slide. Longest increasing subsequence is a dynamic programming problem.
3In 'minimum size subarray with sum ≥ target', why does the pattern require the elements to be positive?
Negative numbers overflow the running sum
✓ The window sum must change monotonically as the window grows or shrinks, or the shrink decision is meaningless
It doesn't - the pattern works for any integers
Because the answer would be negative otherwise
With positives, expanding always raises the sum and shrinking always lowers it, so 'shrink while valid' is safe. A negative element could make a smaller window have a larger sum, breaking the logic - use prefix sums for that variant.
4In the variable-window template for 'longest valid window', when is it safe to record the answer?
Immediately after adding the new right element
✓ After the shrink loop finishes, because the window is guaranteed valid there
Only once, after the outer loop ends
Inside the shrink loop, on every iteration
The shrink loop's exit condition is exactly 'window is valid again'. Recording before it may capture an invalid window; recording after it is always safe.
5A window shrink removes character c, but the frequency map still shows counts of zero for old characters. What breaks?
Nothing - zero counts are harmless in every variant
Memory usage only
✓ Any check that uses the map's size as the distinct-element count
The right pointer can no longer advance
For 'at most k distinct' problems the invariant is size(counts) ≤ k. Keys with count zero inflate the size and cause needless shrinking. Delete keys when their count reaches zero.
Frequently asked questions
When should I use a sliding window instead of prefix sums?
Use a sliding window when the tracked quantity changes monotonically as the window grows or shrinks - sums of positive numbers, counts, distinct characters. Use prefix sums when negatives break that monotonicity or when you need arbitrary (non-contiguous-scan) range queries.
What is the difference between a fixed and a variable sliding window?
A fixed window always contains exactly k elements: add one, remove one, update the answer each slide. A variable window grows on every step and shrinks only while a constraint is violated; its size at each position is part of the answer.
Does the sliding window pattern work on subsequences?
No. A window is contiguous by definition. If the problem allows skipping elements (a subsequence), you need a different pattern - usually dynamic programming or greedy with sorting.
How do I choose the window state data structure?
Match it to the constraint: a running number for sums, a frequency map for distinct-character or anagram constraints, a monotonic deque when you need the window's max or min in O(1).