AlgoScope

Variable-Size Window

Grow the right end until a condition holds, then shrink the left end while it still does.

Sliding window, algorithm, intermediate
The right end moves to index 0 and the sum becomes 2. That is still below the target.active 0-0203112234435leftright
The right end moves to index 0 and the sum becomes 2. That is still below the target.active 0-0203112234435leftright

Sliding Window: Shortest run summing to 7

Decision, step 2 of 13

Grow right to index 0. 2 joins, so the sum is 2. Still short of 7.

How sliding window works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(k)

Leads to

Topics that need this one first.

Taught by the same lesson

Sliding Window covers these too, in the same run.