Variable Sliding Window
Expand the right edge greedily. While the window violates the constraint, shrink from the left. Record the answer whenever the window is valid.
Sliding WindowO(n), each index enters and leaves onceNew11 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
longest substring with condition
smallest subarray with sum at least X
at most K distinct
The template
Get this into muscle memory, then adapt the condition per problem.
let l = 0, best = 0;
for (let r = 0; r < n; r++) {
add(a[r]);
while (!valid()) { remove(a[l]); l++; }
best = Math.max(best, r - l + 1);
} Watch Sliding WindowIf you are stuck
The generic hint ladder for this pattern, in order.
- 1The answer is a contiguous range, so think about what breaks it.
- 2Grow until the condition fails, then shrink just enough to restore it.
- 3Both pointers only move right, which is why this is linear, not quadratic.
Drill it
Every problem in the bank that uses this pattern.
0 / 11 solved