cf.completefrontend
SLIDING WINDOW · FOUNDATION

Fixed-size sliding window

Look at every run of k neighboring items by sliding a window one step at a time, adding the item that enters and removing the one that leaves.

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

The idea

A window is a run of neighboring items in a list, such as items 3 to 7. Many questions ask about every window of the same size k: the busiest 5 minutes in a log, the average of the last 10 frame times, the 3 days in a row with the most sales.

The slow way adds up each window from scratch. A list of n items has about n windows, and each costs k additions, so the work is n * k. The sliding way notices that two windows next to each other share all but two items. When the window slides one step right, one item enters on the right and one item leaves on the left.

So you keep a running total, windowSum. Each slide adds the entering item and subtracts the leaving item: two operations instead of k. The whole list takes one pass.

An everyday example

A train window passing fence posts

You sit on a slow train and can see exactly 4 fence posts through your window at a time. You want to know the moment you can see the most red posts. You don't recount all 4 posts each time the train moves. When it moves one post forward, one new post appears on the right and one disappears on the left. If the new one is red, add one to your count; if the one that left was red, take one away.

How the example maps to the code
In the exampleIn the code
The posts you can see right nowThe window nums[right - k + 1] to nums[right]
How many you can see at oncek
Your count of red postswindowSum
A new post appears on the rightwindowSum += nums[right]
A post disappears on the leftwindowSum -= nums[right - k]

From the slow way to fixed-size sliding window

  1. Start with the obvious way: for every start index, add up the k items from there and compare the total with the best so far. There are n - k + 1 windows and each costs k additions. For 100,000 numbers and k = 1,000, that is 99,001,000 additions.
  2. Now look at two windows next to each other, such as nums[2..4] and nums[3..5]. They share nums[3] and nums[4]; only one item differs at each end. Recomputing the shared items from scratch is the waste: k - 1 of the k additions repeat work already done.
  3. So keep the total from the last window and fix it up. When the window slides one step right, the item at right enters and the item at right - k leaves. Adding one and subtracting the other turns the old total into the new one with two operations, whatever k is.
  4. Only the very first window has nothing to start from, so build it with a plain loop over the first k items. After that, slide, update windowSum, and compare it with best. That loop is the fixed-size sliding window.

How it works

  1. Add up the first k items to get the first window's total, windowSum.
  2. Save it as the best so far: best = windowSum.
  3. Slide the window: move right from k to the end of the list.
  4. Add the item that enters, nums[right].
  5. Subtract the item that leaves, nums[right - k], which is now just outside the window.
  6. Compare the new total with best and keep the larger one. After the loop, 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 maxSumOfK(nums, k) {
  2. let windowSum = 0;
  3. for (let i = 0; i < k; i++) windowSum += nums[i];
  4. let best = windowSum;
  5. for (let right = k; right < nums.length; right++) {
  6. windowSum += nums[right];
  7. windowSum -= nums[right - k];
  8. best = Math.max(best, windowSum);
  9. }
  10. return best;
  11. }

How fast it is

TimeO(n)
Extra memoryO(1)

Each item enters the window once and leaves once, and each move costs one addition or subtraction. Only two numbers are stored.

  • Best caseO(n)

    k equals nums.length: there is one window, built by the first loop in n steps, and the slide loop never runs.

  • Average caseO(n)

    Any k: k additions for the first window, then 2 operations for each of the other n - k windows. About n + (n - k) steps.

  • Worst caseO(n)

    A small k, like 1 or 2: almost every step is a slide, close to 2n operations. Still linear, and still independent of the values.

Common mistakes

  • Subtracting nums[right - k + 1] instead of nums[right - k]. That removes an item still inside the window. The leaving item is the one k places behind the entering one.
  • Starting best at 0. If every number is negative, 0 is never a real window total. Start from the first window's total.
  • Forgetting the case nums.length < k, where no full window exists. Decide what to return before the loop.
  • Recounting the window inside the loop, which brings back the slow O(n * k) time.

When to use it

Look for these clues in a problem:

  • The question names a fixed length: "every k consecutive items", "any 7-day stretch", "windows of size k".
  • It asks for the best, the average, or a count over all windows of that size.
  • The items must be next to each other (a subarray or substring), not any subset.
  • A nested loop over every window would be O(n * k) and too slow.

Check yourself

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

Why is the leaving item nums[right - k] and not nums[right - k + 1]?

The new window is nums[right - k + 1] up to nums[right], so nums[right - k + 1] is still inside. The item one place before it, nums[right - k], is the one that just left.

How many windows of size 3 does a list of 8 items have?

6, which is 8 - 3 + 1. The first loop builds one, and the slide loop handles the other 5.

Why start best at the first window's total instead of 0?

If every total is negative, 0 would never be beaten and the code would return a total no window has.

Does the work depend on k?

Hardly. The first window costs k additions and every other window costs 2 operations, so the total is about 2n - k, which is O(n) for any k.

Practice problems

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

Not started

0 of 19 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

The loop keeps one promise at the end of each step: windowSum is the total of nums[right - k + 1] up to nums[right], and best is the largest total of every window seen so far. After the first loop, windowSum is the total of the first window and best equals it, so the promise holds before sliding starts.

Each slide keeps it. Before the slide, windowSum covers nums[right - k] up to nums[right - 1]. Adding nums[right] and subtracting nums[right - k] leaves exactly nums[right - k + 1] up to nums[right], the new window. Then Math.max makes best the largest of the old best and this window.

The loop ends when right passes the last index, after n - k slides. Every window of size k ends at some index from k - 1 to n - 1, and each was checked once, so best is the largest window total of all.

Going deeper

3 more ideas

Why the total stays correct after each slide

Before a slide, windowSum is the total of nums[right - k] up to nums[right - 1]. Adding nums[right] and subtracting nums[right - k] gives the total of nums[right - k + 1] up to nums[right], which is exactly the next window. So windowSum always matches the window, without ever adding up k items again.

Why it takes O(n) time

The first window costs k additions, and each of the other n - k windows costs one addition and one subtraction. That's about n operations in total, whatever k is. Only windowSum and best are stored, so memory is O(1).

Windows that track more than a sum

The window can carry any summary that can be updated when one item enters and one leaves: a count of vowels, a set of seen values, or a map of letter counts. If the summary can't be updated by removing one item (like the largest value in the window), you need a helper such as a monotonic deque.

Work it by hand

Every step in a table, with why

Find the best total of 3 items in a row. Negative numbers make the total drop, and the best window is the very last one.

nums = [3, -1, 6, 2, -4, 5, 1, 4], k = 3

SteprightEntersLeaveswindowSumbestWhat happensWhy
1-3, -1, 6-88Build the first windowThe first loop adds nums[0] to nums[2]: 3 - 1 + 6 = 8. It is the best so far because it is the only one so far.
232378Window [-1, 6, 2]Add nums[3] = 2, subtract nums[0] = 3. The total drops to 7, so best stays 8.
34-4-148Window [6, 2, -4]Adding a negative lowers the total, and removing a negative raises it: 7 - 4 + 1 = 4.
455638Window [2, -4, 5]The 6 leaves the window, so the total drops even though 5 entered.
561228Window [-4, 5, 1]The lowest total so far.
674-41010Window [5, 1, 4]: new bestRemoving -4 adds 4 back: 2 + 4 + 4 = 10. This is the last window, because right has reached the last index.

It returns 10, from [5, 1, 4]. The loop ends after right = 7, the last index: every one of the 6 windows was checked once.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Fixed-size sliding windowO(n)O(1)One pass over every window of a single size k, with a summary you can update when one item enters and one leaves.
Recompute every windowO(n · k)O(1)k is tiny, like 2 or 3, or the summary can't be updated incrementally and no helper structure fits.
Prefix sumsO(n)O(n)You'll ask about many window sizes or many ranges on the same list, so building the prefix array once pays off.

Extra memory: O(1): windowSum, best, and the loop index. The windows are never copied.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Fixed-size sliding window and the other approaches, on a scale where each line up is 10 times more steps.
  • Fixed-size sliding window, Prefix sums O(n)
  • Recompute every window O(n · k)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Fixed-size sliding window101,0001 million
Recompute every window1001 million1 trillion
Prefix sums101,0001 million

Inputs that need care

5 tricky inputs
k bigger than the list: nums = [1, 2], k = 3
The first loop reads nums[2], which is undefined, and 1 + 2 + undefined is NaN, so it returns NaN. Check nums.length < k first and decide what to return, such as null.
k equal to the list length
One window: the first loop adds every item, the slide loop doesn't run, and the total of the whole list is returned.
All negative: nums = [-5, -2, -8, -1], k = 2
The windows total -7, -10, and -9, and it returns -7. Starting best from the first window, not from 0, is what makes this right.
k = 0
The first window is empty with total 0, and each slide adds and subtracts the same item, so it returns 0. Most callers should reject k < 1.
Decimal values like frame times 0.1, 0.2, 0.3
Decimals can't be stored exactly, so 0.1 + 0.2 + 0.3 is 0.6000000000000001, and after many slides the error can grow. Round when displaying, or rebuild the total from scratch now and then.

Variations and follow-ups

Twists interviewers add

Moving average

Divide windowSum by k after each slide to get the average of the last k values, like a 7-day average line on a chart or the average of the last 60 frame times.

Counting inside the window

Instead of a sum, keep a count: add 1 when a vowel enters and subtract 1 when a vowel leaves. Any summary that can be updated for one item in and one item out works the same way.

Largest item in each window

The largest value can't be updated by subtracting the item that leaves. A monotonic deque keeps the indexes of possible maximums in decreasing order, so each window's maximum is at the front, still in O(n) total.

Prefix sums

Store prefix[i], the total of the first i items. Any window total is then prefix[right + 1] - prefix[right + 1 - k]. This uses O(n) memory but answers many different window questions on the same list quickly.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a fixed length in the question: "every k consecutive", "any 7-day stretch", "windows of size k", together with "maximum", "average", or "how many".
  • Explain the slide in one sentence: "when the window moves right by one, nums[right] enters and nums[right - k] leaves, so I add one and subtract the other". Then point out that right - k is the item just outside the new window.
  • Test by hand: k equal to the length (one window), all negative numbers (best must not start at 0), and k bigger than the length.
  • Expect the follow-up "what if you need the maximum in each window instead of the sum?". The answer is a monotonic deque, because a maximum can't be updated by subtracting the item that leaves.

Where frontend code uses it

The same idea in real UI code
  • A performance overlay that shows the average frame time over the last 60 frames keeps a running total, adding the newest frame time and subtracting the one that dropped out.
  • Rate limiting in a client, such as "at most 5 requests per second", counts events inside a time window that slides as time passes.
  • Charts in analytics dashboards often draw a moving average, such as a 7-day average line, which is a fixed-size sliding window over daily values.

Related algorithms