Fixed Sliding Window
Compute the first window, then for every step add the entering element and remove the leaving one instead of recomputing.
Sliding WindowO(n) time, O(1) or O(alphabet) spaceNew3 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
subarray of size k
max average of k elements
all anagrams of a pattern
The template
Get this into muscle memory, then adapt the condition per problem.
let sum = 0, best = -Infinity;
for (let i = 0; i < n; i++) {
sum += a[i];
if (i >= k) sum -= a[i - k];
if (i >= k - 1) best = Math.max(best, sum);
} Watch Sliding WindowIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Recomputing each window is O(n*k). What stays the same between windows?
- 2Only two elements change when the window slides.
- 3Guard the first k-1 iterations where the window is not full yet.
Drill it
Every problem in the bank that uses this pattern.
0 / 3 solved