What a sliding window is
Many array problems ask about a contiguous piece of the array: the largest sum of 3 neighbouring elements, the longest run that stays under a limit, the shortest run that reaches a target. Checking every possible subarray from scratch is slow, because the subarrays overlap and the same elements are added up again and again.
A sliding window avoids that. You keep two indices, left and right, that mark a stretch of the array, and some information about that stretch, usually its sum or a count of its contents. To move on, you push right forward to take in one new element and, when needed, push left forward to drop an old one. Each move updates the information with one small step instead of recomputing it.
The indices never move backwards. Each one travels across the array at most once, so a pass takes O(n) time, where a nested search over all subarrays takes O(n²).
Use it when the problem is about a contiguous subarray or substring and the answer depends on a property of the whole window that can be updated cheaply, such as a sum, a length, or the number of distinct values.
Fixed-size windows
When the window length k is given, the window moves in lockstep: one element enters on the right as one leaves on the left. This function finds the largest sum of any k consecutive elements:
function maxSumOfK(nums: number[], k: number): number {
if (k > nums.length) return 0;
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += nums[i];
}
let best = windowSum;
for (let right = k; right < nums.length; right++) {
windowSum += nums[right];
windowSum -= nums[right - k];
best = Math.max(best, windowSum);
}
return best;
}
The first loop builds the sum of the first window. The second loop slides it: it adds the new element at right and subtracts the one that just fell out, at right - k. For [2, 1, 5, 1, 3, 2] with k = 3, the window sums are 8, 7, 9 and 6, so maxSumOfK returns 9.
Variable-size windows
Often the length isn't given. Instead there is a rule the window must obey, and you want the longest (or shortest) window that obeys it. The pattern has three parts:
- Expand: move
rightforward and add that element to the window's data. - Shrink: while the window breaks the rule, move
leftforward and remove that element from the data. - Record: the window is valid again, so compare its length
right - left + 1with the best so far.
Here is the longest subarray of positive numbers whose sum is at most S:
function longestAtMostS(nums: number[], S: number): number {
let left = 0, sum = 0, best = 0;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum > S) {
sum -= nums[left];
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}
With nums = [3, 2, 5, 2, 2, 1, 1, 3, 1, 2] and S = 11, the function returns 6. With [5, 6] and S = 3 it returns 0: every element alone is too big, so the window empties itself each time.
The inner while sits inside the for, but the code is still linear. left only ever moves forward and can't pass right by more than one step, so across the whole run the while body runs at most n times.
Why the rule needs the right kind of data
Shrinking from the left works because removing an element moves the window toward being valid. With positive numbers, removing one lowers the sum. If the array can hold negative numbers, removing an element may raise the sum, and this simple pattern no longer applies.
When the rule is about contents, such as "at most K distinct values", the window's data is a Map from each value to its count. The window is valid when map.size is at most K. Removing an element lowers its count, and a count of 0 means the key should be deleted so the size stays honest.
TypeScript details
- Indices are plain numbers. TypeScript has no separate integer type, and
numberis a double. Indices and sums are exact as long as they stay below 2^53, which is far beyond array sizes. - Out-of-range reads give
undefined.nums[nums.length]doesn't throw. It evaluates toundefined, and arithmetic on it givesNaN. Keep loop bounds exact, and checkright < nums.lengthbefore readingnums[right]inwhileconditions. - Types disappear at run time. Annotations such as
nums: number[]help the compiler check your code, but the compiled JavaScript has none of them. - Multiple declarations.
let left = 0, sum = 0, best = 0;declares three variables at once. Each is inferred as anumber.
Common mistakes
- Off-by-one window length. A window from
lefttoright, both included, has lengthright - left + 1. - Resetting the window. Setting
sumorrightback to zero for each newleftturns the technique back into a nested loop. - Forgetting to remove what leaves. Moving
leftwithout subtractingnums[left]leaves a stale sum. - Recording before the window is valid. Compare lengths after the shrinking loop, not before.
- Using
ifinstead ofwhileto shrink. One removal may not be enough to restore the rule.
Key takeaways
- A sliding window keeps a running summary of a contiguous stretch and updates it in constant time per move.
- Both indices only move forward, so the whole scan is
O(n). - Fixed windows add one element and drop one in the same step. Variable windows expand first, then shrink until the rule holds again.
- Pick the window's data to fit the rule: a sum for limits on totals, a
Mapof counts for limits on distinct values.