cf.completefrontend
SLIDING WINDOW · CORE

Variable-size sliding window

Grow a window to the right and shrink it from the left whenever it breaks a rule, to find the longest or shortest run of items that follows the rule.

Time O(n)Space O(1)14 practice problemsStep-through picture

The idea

Some questions ask for the longest or shortest run of neighboring items that follows a rule: the longest stretch of requests that fits in a byte budget, the shortest burst of sales that reaches a goal. The window's size isn't fixed: it's what you are looking for.

The window has two edges, left and right, and both only move right. Each step moves right one item further, so the window grows. If the window now breaks the rule, move left right, removing items from the start, until the rule holds again. After that, the window is valid, so compare its size with the best answer.

This works when the rule behaves nicely: if a window breaks the rule, every bigger window that contains it breaks it too. For example, with non-negative numbers, adding more items can only raise the total, so a total over the limit stays over the limit as the window grows.

An everyday example

A caterpillar crawling along a branch

A caterpillar wants to stretch over as many leaves as possible, but it can only carry 10 grams of leaves at once. It reaches forward with its head and grabs the next leaf. If the load is now too heavy, it pulls its tail forward and drops leaves from the back until the load is light enough again. It never moves backward. At each moment, you measure how long it is.

How the example maps to the code
In the exampleIn the code
The caterpillar's headright
The caterpillar's tailleft
The weight of the leaves it holdswindowSum
Grabbing the next leafwindowSum += nums[right]
Dropping a leaf from the backwindowSum -= nums[left]; left++
Its length right nowright - left + 1

From the slow way to variable-size sliding window

  1. Start with the obvious way: try every start left, extend the end one item at a time while keeping a running sum, and stop when the sum goes over limit. That checks up to n * (n + 1) / 2 windows, which is O(n^2), and most of that work repeats.
  2. Look at one end index right at a time. With non-negative numbers, removing items from the left can only lower the total. So if the window from some start to right fits the limit, every later start fits too. The valid windows ending at right are exactly those starting at or after one smallest valid start.
  3. Now move right one step further. The total for any fixed start can only grow, so a start that was too early for right is still too early for right + 1. The smallest valid start never moves backward. You can keep left from the last step and nudge it forward only when needed.
  4. So each step adds nums[right], then removes items from the left while the window is over the limit, and measures right - left + 1. Both edges only move forward. That loop is the variable-size sliding window.

How it works

  1. Start with an empty window: left = 0, windowSum = 0, best = 0.
  2. Move right across the list. Each step adds nums[right] to the window.
  3. While the window breaks the rule (windowSum > limit), remove nums[left] and move left right.
  4. Now the window left..right follows the rule. Its size is right - left + 1.
  5. If that size beats best, save it.
  6. After right reaches the end, return best.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function longestWithinLimit(nums, limit) {
  2. let left = 0;
  3. let windowSum = 0;
  4. let best = 0;
  5. for (let right = 0; right < nums.length; right++) {
  6. windowSum += nums[right];
  7. while (windowSum > limit) {
  8. windowSum -= nums[left];
  9. left++;
  10. }
  11. best = Math.max(best, right - left + 1);
  12. }
  13. return best;
  14. }

How fast it is

TimeO(n)
Extra memoryO(1)

right moves n times and left moves at most n times in total, so each item is added once and removed at most once. Only a few numbers are stored.

  • Best caseO(n)

    The whole list fits the limit, like [1, 2, 1] with limit = 10: left never moves and each step does one addition.

  • Average caseO(n)

    Any list of non-negative numbers: each item is added once and removed at most once, so at most 2n updates.

  • Worst caseO(n)

    Every item is over the limit by itself, like [9, 8, 7] with limit = 5: each item is added and removed right away, exactly 2n updates.

Common mistakes

  • Using it with negative numbers. Adding an item can then lower the total, so a too-big window can become valid again and shrinking from the left can skip the answer. Use prefix sums with a hash map instead.
  • Writing if instead of while for the shrink step. One removal may leave the window still too big.
  • Measuring the window before shrinking it, which counts a window that breaks the rule.
  • Moving left back or resetting it to right after a bad window. That throws away valid windows and can make the time O(n²).

When to use it

Look for these clues in a problem:

  • The question asks for the longest or shortest subarray or substring that meets a condition.
  • The condition is about the whole window: a sum at most a limit, at most k zeros, no repeated characters.
  • Making a window bigger can only make the condition worse, and making it smaller can only make it better.
  • The numbers are non-negative (for sums), so the running total moves in one direction as the window grows.

Check yourself

Answer each one in your head first, then open it.

Why must the shrink step be while and not if?

One big item can push the total over by more than the leftmost item's value. In the trace, adding 6 needed three removals before the window fit again.

Why does left never need to move back?

A start that made the window too big for one right makes it even bigger for a later right, because the numbers are non-negative. So no skipped start can become valid again.

How many times can windowSum change on a list of 1,000 numbers?

At most 2,000 times: 1,000 additions as right moves, and at most 1,000 subtractions as left moves.

What does best hold if every single item is over limit?

0. Each step removes the new item at once, so the window is always empty and right - left + 1 is 0.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 14 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

After the while loop at each step, two promises hold. First, windowSum is the total of nums[left] up to nums[right], and it is at most limit. Second, left is the smallest start that makes a valid window ending at right. The first promise follows from adding each item once and subtracting each removed item once.

The second promise rests on the numbers being non-negative. The while loop only removes an item when the window that still includes it is over the limit; any window ending at right that starts even earlier contains that window and is at least as large, so it is invalid too. And a start skipped at an earlier right was too early then, so with an extra item it is still too early now.

So for each right, the longest valid window ending there is exactly left..right, and best takes the largest of these. Every valid window ends at some right, so best is the longest valid window overall. The loop ends because right moves n times and left can move at most n times in total.

Going deeper

3 more ideas

Why left never needs to move back

Suppose the window from left to right is too big, so you moved left forward. Could a window that starts before the new left and ends at a later right be valid? It would contain the window that was too big, and with non-negative numbers its total is at least as large, so it's too big too. So the starts you skipped never come back into play, and both edges only move forward.

Why it takes O(n) time even with a loop inside a loop

The inner while loop looks like it could make this O(n²). But each time it runs, left moves forward, and left can move forward at most n times in the whole run. So across all steps, the inner loop runs at most n times in total. Each item is added once and removed at most once.

Longest versus shortest

For the longest valid window, shrink while the window is invalid, then measure. For the shortest window that reaches a goal (such as a total of at least target), it's flipped: after adding nums[right], while the window is valid, measure it, then shrink it to see if a shorter one still works.

Work it by hand

Every step in a table, with why

Find the longest run with a total of at most 6. One big item forces three removals in one step, and the last window ties the best.

nums = [4, 1, 1, 6, 2, 3, 1], limit = 6

Steprightnums[right]RemovedleftwindowSumbestWhy
104-041The window [4] fits, so its size, 1, is the best so far.
211-052[4, 1] totals 5, still within 6.
321-063[4, 1, 1] totals exactly 6. 6 > 6 is false, so no shrinking: size 3.
4364, 1, 1363Adding 6 makes 12. The while loop removes 4 (8 left), 1 (7 left), and 1 (6 left). One if would have stopped too early.
54264236 + 2 = 8 is over, so 6 is removed. The window is [2].
653-453[2, 3] fits, size 2.
761-463[2, 3, 1] totals 6, size 3. That ties best, so best stays 3.

It returns 3: both [4, 1, 1] and [2, 3, 1] have 3 items and total 6. The loop ends when right passes the last index; left moved 4 times in all.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Variable-size sliding windowO(n)O(1)The numbers are non-negative (or the rule only gets worse as the window grows) and you need the longest or shortest valid run.
Every start, extended to the rightO(n^2)O(1)The list is small, or the rule isn't monotone, so shrinking from the left could skip answers.
Prefix sums plus binary searchO(n log n)O(n)With non-negative numbers the prefix sums are sorted, so for each right you can binary search the earliest valid start. Useful when you'll ask many limits on the same list.

Extra memory: O(1): left, windowSum, and best. The window is described by its two edges, never copied.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Variable-size sliding window and the other approaches, on a scale where each line up is 10 times more steps.
  • Variable-size sliding window O(n)
  • Every start, extended to the right O(n^2)
  • Prefix sums plus binary search O(n log n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Variable-size sliding window101,0001 million
Every start, extended to the right1001 million1 trillion
Prefix sums plus binary search339,96620 million

Inputs that need care

5 tricky inputs
An empty list
The loop doesn't run and it returns 0.
One item over the limit: nums = [9], limit = 5
The while loop removes the 9, leaving left = 1 and an empty window of size 0, so it returns 0: no valid window exists.
Negative numbers: nums = [4, -3, 2], limit = 3
The whole list totals 3 and fits, but the code drops the 4 as soon as it sees it and returns 2. Negative numbers break the rule that shrinking only helps, so use prefix sums with a sorted structure instead.
Zeros with limit = 0: nums = [0, 0, 0]
0 > 0 is false, so nothing is removed and it returns 3.
A negative limit: nums = [2, 3], limit = -1
Even the empty window's total, 0, is over the limit, so the while loop runs past right, reads nums[2] as undefined, and windowSum becomes NaN. It happens to return 0, but add left <= right to the while condition or reject such limits up front.

Variations and follow-ups

Twists interviewers add

Shortest window that reaches a goal

For the shortest run with a total of at least target, flip the order: after adding nums[right], while the window is valid, record its size and then remove nums[left] to try a shorter one. The same forward-only argument gives O(n).

At most k bad items

Count something instead of summing: for the longest run with at most k zeros, add 1 when a zero enters, and shrink while the count is over k. Many "flip at most k" questions are this window.

Counting valid windows

To count every valid subarray rather than find the longest, add right - left + 1 after the shrink step: those are all the valid windows that end at right. For example, counting runs whose product is below a limit works this way.

Windows over content

When the rule is about which values the window holds, like "at most k different letters", keep a frequency map of the window. The sliding is the same; only the bookkeeping changes.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "longest" or "shortest" plus "subarray" or "substring" plus a condition on the whole run, such as a sum at most limit or at most k zeros.
  • Before coding, check the one property that makes it work and say it out loud: "if a window breaks the rule, any bigger window containing it breaks it too, because the numbers are non-negative".
  • Explain why it's O(n) despite the nested while: left only moves forward and can move at most n times over the whole run, so the inner loop does at most n steps in total.
  • Expect the follow-up "what if the numbers can be negative?". The answer: the window trick no longer works, so use prefix sums, with a hash map for exact sums or a monotonic deque for bounds.

Where frontend code uses it

The same idea in real UI code
  • Fitting as many recent log lines as possible into a fixed byte budget before sending them to a logging service.
  • Finding the longest stretch of a recorded session where frame times stayed under a jank threshold, to report smooth periods in a performance tool.
  • Text tools that find the longest line segment that fits a width, measuring word widths as the window grows and shrinks.

Related algorithms