Course contents
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.
01Fixed-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.
02Variable-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.
03Where it goes wrong
| 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 problems
Tagged by pattern, so you can tell whether you learned the idea or just the example.
- Maximum sum subarray of size kFixed windowEasy
- Longest substring without repeating charactersVariable windowMedium
- Minimum size subarray with sum at least targetVariable windowMedium
- Longest repeating character replacementVariable window + countsMedium
- Sliding window maximumFixed window + dequeHard
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 Arrays solo, or share a room code and battle friends on it.