AlgoViz
HomeSliding Window

Variable-Size Window

Medium

Grow while valid, shrink when broken

Problem

Learn the variable-size sliding window: expand the right edge and shrink the left edge to maintain a constraint (like a max sum or distinct-count limit).

In simple words

Stretch the window on the right and pull in the left whenever a rule is broken.

The idea

Push the right edge outward one element at a time, updating whatever you are tracking; whenever the window becomes invalid, pull the left edge in until it is valid again. Each pointer only ever moves forward, so despite the nested loop the whole sweep is O(n).

The trick

  • Both pointers move forward only — that is why the total work is linear, not quadratic.
  • Decide up front whether you record the answer while valid (longest) or while invalid (shortest).
  • Whatever the window tracks must be updatable in O(1) on both add and remove.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

2
1
5
1
1
0
1
2
3
4

Step 1 of 2. Here's the example — longest subarray sum <= 5 in [2,1,5,1,1] Values: 2, 1, 5, 1, 1.

1/2
Optimal
timeO(n)spaceO(1)
1l=02for r: add nums[r]3  while constraint broken: remove nums[l]; l++4  update answer with (r-l+1)

Input

array
[2, 1, 5, 1, 1]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
longest subarray sum <= 5 in [2,1,5,1,1]
Output:
[1,1,1] length 3

Finished the walkthrough? Add it to your streak.