Sliding Window
The sliding window pattern solves contiguous subarray and substring problems in O(n) by updating a running result instead of recalculating it.
The sliding window pattern solves problems about a contiguous part of an array or string: a subarray or a substring. It keeps a "window" over part of the input and slides it along, updating the result as items enter and leave instead of recalculating it each time.
The idea
Suppose you want the largest sum of any 3 consecutive numbers. The brute-force way adds up every group of 3 separately. But two neighbouring groups share two of their three numbers:
[ 2 1 5 ] 1 3 2 sum = 8
2 [ 1 5 1 ] 3 2 sum = 8 - 2 + 1 = 7To move the window one step, subtract the number that left and add the number that entered. Each step is O(1), whatever the window size.
When to use it
- The problem says subarray, substring or consecutive.
- It asks for the longest, shortest, largest or smallest such range, or to count them.
- A brute-force solution would check every possible start and end.
It does not apply to subsequences, where items need not be adjacent.
Form 1: fixed-size window
The window always holds exactly k items.
function maxWindowSum(numbers, k) {
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += numbers[i];
}
let best = windowSum;
for (let i = k; i < numbers.length; i++) {
windowSum += numbers[i] - numbers[i - k]; // add the new item, drop the oldest
best = Math.max(best, windowSum);
}
return best;
}Walkthrough
maxWindowSum([2, 1, 5, 1, 3, 2], 3):
| Window | Enters | Leaves | Sum | best |
|---|---|---|---|---|
| 2, 1, 5 | 8 | 8 | ||
| 1, 5, 1 | 1 | 2 | 7 | 8 |
| 5, 1, 3 | 3 | 1 | 9 | 9 |
| 1, 3, 2 | 2 | 5 | 6 | 9 |
Each move is one addition and one subtraction, whether the window holds 3 items or 3,000.
Form 2: variable-size window
The window grows from the right and shrinks from the left whenever it stops being valid. This form finds the longest or shortest range that satisfies a condition.
// Length of the longest subarray whose sum is at most `limit`.
// Assumes every number is positive.
function longestWithinLimit(numbers, limit) {
let start = 0;
let windowSum = 0;
let best = 0;
for (let end = 0; end < numbers.length; end++) {
windowSum += numbers[end]; // grow
while (windowSum > limit) { // shrink until valid again
windowSum -= numbers[start];
start++;
}
best = Math.max(best, end - start + 1);
}
return best;
}The steps are always the same: add the item at end, shrink from start while the window is invalid, then record the result.
Walkthrough
longestWithinLimit([1, 2, 1, 1, 5, 1], 4):
| end (value) | Sum after adding | Shrinking | Window | best |
|---|---|---|---|---|
| 0 (1) | 1 | 1 | 1 | |
| 1 (2) | 3 | 1, 2 | 2 | |
| 2 (1) | 4 | 1, 2, 1 | 3 | |
| 3 (1) | 5 | Drop 1: sum 4 | 2, 1, 1 | 3 |
| 4 (5) | 9 | Drop 2, 1, 1 and 5: sum 0 | empty | 3 |
| 5 (1) | 1 | 1 | 3 |
At end = 4 the single value 5 is larger than the limit, so the window shrinks until it is empty. That is handled without a special case: an empty window has length 0, which never beats best.
Longest or shortest
The variable-size form comes in two versions, and they differ in when the window shrinks and when the answer is recorded.
| Longest valid window | Shortest valid window | |
|---|---|---|
| Shrink | While the window is invalid | While the window is valid |
| Record the answer | After shrinking, when it is valid again | Inside the shrink loop, before each removal |
| Example | Longest Substring Without Repeating Characters | Minimum Size Subarray Sum |
Getting these the wrong way round is the most common error with this pattern.
A window with a map inside
A sum is enough when the condition is about a total. When it is about what the window contains, keep a map of counts and update it as items enter and leave.
// Length of the longest substring with at most k different characters.
function longestWithKDistinct(text, k) {
const counts = new Map();
let start = 0;
let best = 0;
for (let end = 0; end < text.length; end++) {
counts.set(text[end], (counts.get(text[end]) ?? 0) + 1);
while (counts.size > k) {
const leaving = text[start];
counts.set(leaving, counts.get(leaving) - 1);
if (counts.get(leaving) === 0) counts.delete(leaving);
start++;
}
best = Math.max(best, end - start + 1);
}
return best;
}For "eceba" with k = 2 the answer is 3, the substring "ece". Deleting a character from the map when its count reaches zero is what keeps counts.size equal to the number of different characters in the window.
What to keep for the window
| The condition is about | Keep | Cost to update |
|---|---|---|
| A total | A running sum | O(1) |
| How many of each item | A map of counts | O(1) |
| How many different items | The size of that map | O(1) |
| Whether an item repeats | A set, or a map of last positions | O(1) |
| The largest or smallest item | A queue kept in sorted order | O(1) on average: see Sliding Window Maximum |
If the thing you need cannot be updated cheaply as one item enters and one leaves, the pattern does not help.
Complexity
- Time: O(n). There is a
whileloop inside aforloop, but it is not O(n²).startonly ever moves forward, so across the whole run it advances at mostntimes. Every item enters the window once and leaves at most once. - Space: O(1) for sums and counts. If the window needs a map or set to track its contents, the space is the size of that structure.
Common mistakes
- Using it when shrinking does not help. The variable-size form needs this property: if a window is invalid, making it larger keeps it invalid. With negative numbers and a sum condition that is not true, so the pattern does not apply.
- Off-by-one in the window length. A window from
starttoendinclusive holdsend - start + 1items. - Recalculating inside the loop. Calling something like
sliceand summing it for each position puts the O(n²) cost back. - Shrinking with
ifinstead ofwhile. One new item can make room for several to leave, or force several out. - Recording at the wrong moment. See the longest-or-shortest table above.
- Leaving stale entries in the map. If a count reaches zero and the key is not deleted, the map's size no longer says how many different items are in the window.
When the numbers can be negative, a window is the wrong tool for sums. Use prefix sums instead.
Practise
- Maximum Sum Subarray of Size K (easy): the fixed-size form.
- Longest Substring Without Repeating Characters (medium): the longest valid window.
- Minimum Size Subarray Sum (medium): the shortest valid window.
- Minimum Window Substring (hard): a map of what is still needed.
- Sliding Window Maximum (hard): tracking the largest item.
Practice problems
| Problem | Difficulty | Time | Space | Read |
|---|---|---|---|---|
| Maximum Sum Subarray of Size K | easy | O(n) | O(1) | Quick read: 3 min |
| Longest Substring Without Repeating Characters | medium | O(n) | O(k) | Short read: 4 min |
| Minimum Size Subarray Sum | medium | O(n) | O(1) | Medium read: 6 min |
| Minimum Window Substring | hard | O(n + m) | O(m) | Medium read: 7 min |
| Sliding Window Maximum | hard | O(n) | O(n) | Medium read: 8 min |