The Sliding Window Technique Explained
A sliding window answers questions about every contiguous subarray without visiting every contiguous subarray. The insight is small and powerful: consecutive windows overlap almost entirely, so the next answer is the previous answer plus one element and minus one element.
Fixed-size windows
"Maximum sum of any k consecutive elements." The naive solution recomputes each window from scratch: n windows x k additions = O(n x k). But window i+1 shares k-1 elements with window i, so recomputing is pure waste.
int maxSumOfSizeK(int[] a, int k) {
int sum = 0;
for (int i = 0; i < k; i++) sum += a[i]; // first window
int best = sum;
for (int end = k; end < a.length; end++) {
sum += a[end] - a[end - k]; // add new, drop old
best = Math.max(best, sum);
}
return best;
}One addition and one subtraction per step: O(n) time, O(1) space. Every fixed-window problem is a variation on this — track a sum, a count, a maximum, or a frequency map instead of the sum.
Variable-size windows
When the question is "the longest / shortest subarray such that ...", the window size is not given — you have to discover it. The shape is always the same: expand the right edge greedily; shrink the left edge while the window is invalid.
int longestUnique(String s) {
Set<Character> window = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
// shrink until the window is valid again
while (window.contains(s.charAt(right))) {
window.remove(s.charAt(left++));
}
window.add(s.charAt(right));
best = Math.max(best, right - left + 1);
}
return best;
}The inner while looks like it makes this quadratic, but it does not: left only ever moves forward, so across the whole run it advances at most n times. Each index enters the window once and leaves once — O(n) total. Being able to explain that amortised argument is usually the point of the question.
The template
Expand right in the outer loop. Shrink left in an inner while that runs as long as the window is invalid. Record the answer at the point where the window is valid. Almost every variable-window problem fits that skeleton.
Where it goes wrong
Negative numbers in a 'longest subarray with sum ≤ k' problem
Sliding window assumes that shrinking the window moves the metric in a predictable direction. With negative values, removing an element can increase the sum, so the assumption breaks. Use prefix sums with a hash map instead.
Recording the answer at the wrong moment
For a longest window, record after shrinking, when the window is valid. For a shortest window, record inside the shrink loop, just before the window becomes invalid. Getting this backwards is the most common off-by-one in window problems.
| The question says | Window type | Track |
|---|---|---|
| "of size k" | Fixed | Running sum or frequency map |
| "longest ... such that" | Variable | Expand right, shrink while invalid |
| "shortest ... such that" | Variable | Expand right, record while shrinking |
| "count the subarrays where ..." | Variable | Add (right - left + 1) per step |
Key takeaways
- Consecutive windows overlap, so update the previous answer instead of recomputing it.
- Fixed window: add the entering element, subtract the leaving one.
- Variable window: expand right, shrink left while invalid — O(n) because left only moves forward.
- Negative numbers break the shrink assumption; reach for prefix sums there instead.
Practice
| Problem | Pattern | Level |
|---|---|---|
| Maximum sum subarray of size k | Fixed window | Easy |
| Longest substring without repeating characters | Variable window | Medium |
| Minimum size subarray with sum at least target | Variable window | Medium |
| Longest repeating character replacement | Variable window + counts | Medium |
| Sliding window maximum | Fixed window + deque | Hard |
Frequently asked questions
What is the sliding window technique?
It is a way of answering questions about contiguous subarrays in one pass, by maintaining a window between two indices and updating its answer incrementally as the window moves rather than recomputing it.
Why is a variable sliding window O(n) and not O(n squared)?
The left pointer never moves backwards. Across the whole run it advances at most n times in total, so the inner shrink loop does at most n work overall, not n work per outer step.
When does sliding window not work?
When the array can contain negative values and the condition involves a sum, or when the subarray does not have to be contiguous. In both cases the window's monotonic behaviour is lost.
Test yourself on Arrays
Reading is not recall. Take a timed quiz on this topic solo, or share a room code and battle friends on it.
⚡ Start the Arrays quiz