APPLIED CODING YouTube

Applied Coding › Guides › Sliding Window

Sliding window — stop recalculating the same range

The biggest average of three numbers in a row. Adding up every range from scratch works, and keeps adding the same numbers again. A window that slides — one number leaves, one comes in — does the whole list in one pass.

Pattern: Sliding Window · Language: Python · Reading time ≈ 12 min · Video 3:47
The narrator beside a row of numbers with a yellow window over 1, 5, 2, under the title SLIDING WINDOW

Watch the video version

Under four minutes: the sums done the slow way, the window pulled in from the storeroom and pushed along the row, then the code built line by line beside it. The written version below keeps the whole program in one place and lets you slide your own window.

Watch on YouTube

1 · The problemThe biggest average of three

A row of numbers: 1, 5, 2, 3, 7, 1, 4. Which three numbers next to each other have the biggest average?

The narrator points at a row of seven boxes, 1 5 2 3 7 1 4, under the question BIGGEST AVERAGE?; an empty scoreboard stands to the right
Seven numbers, ranges of three, one question.

Stated in general: given a list of numbers and a size k, find the largest average of any k consecutive numbers. Every range has the same size, so the biggest average is simply the biggest sum, divided by k once at the end.

2 · The obvious ideaThe obvious way: add up every range

Easy. Take the first three: 1 + 5 + 2 = 8. Write down 8 / 3. Next three: 5 + 2 + 3 = 10. Next: 2 + 3 + 7 = 12. Then 3 + 7 + 1 = 11, and 7 + 1 + 4 = 12. The best is 12, an average of 4.

The first three boxes lit yellow, 1 + 5 + 2 = 8 written above and 8 / 3 on the scoreboard
The first range: 1 + 5 + 2 = 8.
The next three boxes lit, 5 + 2 + 3 = 10, and 10 / 3 written beside 8 / 3
The next range, added up from nothing again: 5 + 2 + 3 = 10.

In code, a loop over every starting position with a loop inside it that adds up k numbers:

def max_average_every_window(nums, k):    best = None    for start in range(len(nums) - k + 1):        total = 0        for j in range(start, start + k):            total += nums[j]        if best is None or total > best:            best = total    return best / k

It gives the right answer — 4.0 on this row. But the inner loop runs k times for every one of the n − k + 1 ranges.

3 · The observationDidn't I just calculate that?

Look at two neighbouring ranges: 5 + 2 + 3 and 2 + 3 + 7. The 2 and the 3 are in both. They didn't change — so why add them up again?

The 2 and the 3 circled in red inside a frame that spans 2, 3, 7; the scoreboard lists 8/3, 10/3, 12/3, 11/3, 12/3
These two didn't change. Every range shares all but one number with the one before it.

With ranges of three, two of the three numbers are always repeats. With ranges of a thousand, 999 of them are. Almost all of the work is work you already did.

4 · The discoveryA window over three numbers

So stop treating each range as a new problem. Keep one window the size of a range, and remember the sum of what is inside it.

The narrator pulls a tall glass frame in from the edge of the room, beside the row of numbers; BIGGEST AVERAGE? and K = 3 above
In the video the window is an object: he pulls it in from the storeroom at the edge of the frame.
The window lies over the first three boxes, 1, 5 and 2, with 1 + 5 + 2 = 8 above it; the narrator leans on it
The window covers exactly k numbers. Its sum is the only thing we need to remember.

5 · The moveOne leaves, one comes in

Push the window one step to the right. What actually changes? One number leaves on the left — the 1. One number comes in on the right — the 3. Everything else stays.

The window now over 5, 2, 3; the 1 behind it marked OUT in red, the 3 marked IN
One leaves, one comes in.

So the new sum doesn't need three additions. Take the old sum, subtract what left, add what came in: 8 − 1 + 3 = 10.

Above the window: 8 − 1 = 7, then 7 + 3 = 10 in blue; a new scoreboard reads START = 10
I don't need to calculate everything. I just change what changed.

Keep pushing. Each step, the number that leaves is the one that was first in the window, and the one that enters is the next one on the right:

WindowLeavesComes inSumBest so far
1 5 2——88
5 2 3138 − 1 + 3 = 1010
2 3 75710 − 5 + 7 = 1212
3 7 12112 − 2 + 1 = 1112
7 1 43411 − 3 + 4 = 1212
The window pushed further along the row; a scoreboard ledger reads START = 10, −5 +7 → 12, −2 +1 → 11, −3 +4 → 12
The scoreboard in the video keeps the same ledger: one subtraction and one addition per step.

Best sum 12, best average 12 / 3 = 4. The same answer as before, with two operations per step instead of three — and with ranges of a thousand, two instead of a thousand.

6 · The nameThis is a sliding window

It just slides along the numbers. That's the name: a sliding window.

SLIDING WINDOW written over the row of numbers, the window back on the first three and the ledger on the scoreboard
Named after it is understood, not before.

When you need to examine ranges of the same size, you don't start from zero every time. You keep the previous answer and update only what changed:

  1. Keep a window

    Its size is fixed. Its sum is the one thing you remember.

  2. Remove what leaves

    Subtract the number that falls out on the left.

  3. Add what enters

    Add the number that comes in on the right.

  4. Update the result

    Is this window the best so far?

SUM = 8 above the window; the 1 leaving on the left marked OUT and the label REMOVE LEFT
Remove what leaves…
SUM = 10 in blue above the window, now over 5, 2, 3; the label UPDATE
…add what enters, and update.
The key idea

If most of the range stays the same, don't do the same work again. Find the part that changed — here one number on each side — and update the answer by that much.

7 · The costWhat it costs

A monitor split in two: RECALCULATE in red with 1 + 5 + 2 = 8, 5 + 2 + 3 = 10, 2 + 3 + 7 = 12; UPDATE in green with START = 8, −1 +3 → 10
The obvious solution calculates every range from scratch. The sliding window reuses the work it already did.

Recalculating does k additions for each of the n − k + 1 ranges: O(n · k). The window adds up the first k numbers once, then does one subtraction and one addition per step: O(n), whatever k is. It keeps two numbers, the window sum and the best: O(1) extra space.

On the monitor: BRUTE FORCE O(N × K) in red and SLIDING WINDOW O(N) in green over a long row of boxes with the window gliding to its end
Instead of doing k work for every position, the window updates in constant time.
Recalculate · n = 100,000, k = 1,00099,001,000numbers read
Slide · same list199,000numbers read

8 · The codeThe code, one move per line

The function gets the numbers and k, the size of the window.

class Solution:    def findMaxAverage(self, nums: List[int], k: int) -> float:

The first window

Add up the first k numbers. That is the window's sum, and it is also the best so far.

class Solution:    def findMaxAverage(self, nums: List[int], k: int) -> float:        window = sum(nums[:k])        best = window

Slide

For every new number on the right — index i from k to the end — add it, and subtract the one that just left on the left. The one leaving is exactly k places behind the one entering: nums[i - k].

class Solution:    def findMaxAverage(self, nums: List[int], k: int) -> float:        window = sum(nums[:k])        best = window        for i in range(k, len(nums)):            window += nums[i] - nums[i - k]

One add, one subtract. Not k additions.

Beside the narrator, the editor with the line window += nums[i] - nums[i - k] lit; under it the window over 5, 2, 3 and the chips window = 10, best = 8
The slide line runs on the copy of the row under the code: window = 10, best still 8.

Keep the best

        for i in range(k, len(nums)):            window += nums[i] - nums[i - k]            best = max(best, window)

Divide once

At the end, divide the best sum by k. Just once — comparing sums is the same as comparing averages when every window has the same size.

class Solution:    def findMaxAverage(self, nums: List[int], k: int) -> float:        window = sum(nums[:k])        best = window        for i in range(k, len(nums)):            window += nums[i] - nums[i - k]            best = max(best, window)        return best / k

The whole thing

class Solution:    def findMaxAverage(self, nums: List[int], k: int) -> float:        window = sum(nums[:k])        best = window        for i in range(k, len(nums)):            window += nums[i] - nums[i - k]            best = max(best, window)        return best / k

Run it on the row: the window sums are 8, 10, 12, 11, 12; the best is 12; 12 / 3 = 4.0. On a second example, [1, 12, -5, -6, 50, 3] with k = 4, it returns 12.75: the best window is 12, −5, −6, 50, whose sum is 51, and 51 / 4 = 12.75.

The whole program on the editor with return best / k lit; under it the window at the end of the row over 7, 1, 4 and the chips window = 12, best = 12
The end of the run: best = 12, and 12 / 3 = 4.
Running it yourself

The signature uses the type hint List[int], as the editor in the video does. In a plain Python file, put from typing import List at the top first (or write list[int] on Python 3.9 and later).

Under the full program on the monitor: O(N) TIME and O(1) SPACE
Every number enters once and leaves once. Two numbers of memory.

9 · The trapThe off-by-one to avoid

The usual mistake is in the one line that matters: the number leaving is nums[i - k]. Write nums[i - k + 1] instead and you subtract a number that is still inside the window, while the one that really left stays in the sum.

The slide line in red with i - k + 1 boxed; under it the window has grown over 1, 5, 2 and the 3, with the 5 crossed out
Off by one, and the window grows: it keeps a number it should drop and drops one it should keep.

On our row the buggy version's sums go 8, 6, 11, 9, 6 — it reports 11 / 3 ≈ 3.67 instead of 4. Nothing crashes, which is what makes it dangerous. Check the index with one concrete step: when i = 3 (the 3 enters), the leaving number must be index 0 (the 1): 3 − 3 = 0.

10 · Try itSlide your own window

The window, step by step

The Python above, translated to run in your browser. Change the numbers and k, step through the slide, and compare how many numbers it reads with recalculating every range. Switch the bug on to watch the off-by-one go wrong.

Press Step.
window –best –average –numbers read by the window 0recalculating every range reads 0

11 · The lessonHow to recognize it

The problem never says "sliding window". What it says is: every range of k consecutive items, or the best / longest / shortest stretch that…. Two questions give it away:

  1. Am I looking at contiguous ranges?

    Neighbouring items, in order — not any subset.

  2. Do neighbouring ranges overlap?

    If the next range is the last one minus one item plus one item, you can update instead of recompute.

DON'T RECALCULATE. UPDATE. FIND THE WORK THAT DIDN'T CHANGE. over the narrator and the row with the window on 2, 3, 7
Don't memorize the code. Remember the movement.
A thought to carry forward

Here the window has a fixed size. In many problems it doesn't: it grows on the right until a rule breaks, then shrinks from the left until the rule holds again. Same two moves — something enters, something leaves — just not in lockstep.

12 · PracticeFour problems, same shape

Don't watch the solution. For each one, decide what the window holds, what you update when a number enters, and what you undo when one leaves.

  • Warm-upMaximum average of k in a row, from scratch

    Close this page and write it. Then count your additions on a list of 100,000 numbers with k = 1,000, and compare with the every-range version.

  • PracticeRanges of size k with an average over a threshold

    Count how many windows of size k have an average at least some threshold. The window is the same; what changes is what you do with each sum.

  • VariationThe most vowels in a substring of length k

    A string instead of numbers. What does the window keep now — and what is "one leaves, one comes in" for letters?

  • ChallengeIs an anagram of one word hidden in another?

    Does some window of the second word use exactly the letters of the first? The window keeps letter counts; the hard part is checking them fast at each step.

The Two Pointers guide's thumbnail: WHY CHECK EVERYTHING?

A close cousin — two pointers →

A window is two positions moving the same way. Two pointers moving toward each other solve a different question: two prices on a sorted shelf that add up to exactly $18, in three checks.

If most of the range stays the same, don't do the same work again.