Fixed-size sliding window in Python lists

Why this matters

Many list questions ask about a block of values that sits side by side. "What is the biggest total of any 3 days in a row?" "What is the average temperature over each 7-day span?" The block is called a window, and its length is k. The window slides along the list one step at a time, so each answer comes from the one before it.

The obvious method adds up all k values again for every window. That repeats work. Two neighbouring windows share most of their values, yet the obvious method adds the shared values twice. The sliding window method uses the overlap. It keeps the total from the last window and changes it with two small steps: add the value that just entered, and remove the value that just left.

This lesson covers windows whose length stays the same. The next lesson covers windows whose length changes. The prefix sums lesson earlier in this module answers range questions from a precomputed table. The sliding window needs no table, only one running total.

The idea

What a window is

A window is a run of values that sit next to each other in the list. Its length is how many values it holds. A fixed-size window keeps the same length k for the whole walk.

Take the list [2, 1, 5, 1, 3, 2] and set k to 3. The windows of length 3 are:

• positions 0 to 2: 2, 1, 5
• positions 1 to 3: 1, 5, 1
• positions 2 to 4: 5, 1, 3
• positions 3 to 5: 1, 3, 2

There are four windows. In general, a list of n values has n - k + 1 windows of length k. Check it here: 6 - 3 + 1 is 4. The first window starts at index 0. The last window starts at index n - k, which is index 3 in this list.

Index means the position of a value. Python counts positions from 0. The first value is at index 0, and the last of six values is at index 5.

The slow way

The direct method computes each window's total from scratch. For each start position, it adds up the k values inside the window. Python's slice a[start:start + k] gives those values, and sum adds them.

Output:

8 7 9 6
max 9

The answer is correct, but count the work. There are n - k + 1 windows, and each one costs k additions. The total is about n * k additions. With n equal to one million and k equal to one thousand, that is about one billion additions. The sliding method below does about one million. The sum function does its additions in fast code inside Python, but it still adds k values for every window, so the count of additions is what the sliding method cuts.

The fast way: add one, remove one

Here is the key observation. Two neighbouring windows differ in only two places. When the window moves from positions 0 to 2 to positions 1 to 3, the value at position 0 leaves and the value at position 3 enters. The two windows share positions 1 and 2.

So the total changes only by the entering value and the leaving value:

new total = old total + value entering - value leaving

Work it by hand with the same list. The first window, 2, 1, 5, has total 8. The window moves right by one. The value entering is a[3], which is 1. The value leaving is a[0], which is 2. The new total is 8 + 1 - 2, which is 7. Check it by adding the new window directly: 1 + 5 + 1 is 7. The two methods agree.

Here is the same walk for all four windows:

Now the general rule. Suppose the window ends at index i. The value entering is a[i]. The window has k values, so it starts at i - k + 1. The value just before that start is a[i - k], and that is the value that just left. So the rule for each new index is:

total = total + a[i] - a[i - k]

The loop has three parts.

1. Add up the first window directly. This costs k additions, and it happens once.
2. For each new index i from k to n - 1, add a[i] and subtract a[i - k].
3. After each step, the total is the sum of the window that ends at i.

Each value is added once when it enters and subtracted once when it leaves. The number of steps is fixed by n, not by k. This is what computer scientists write as O(n), which means the work grows in step with the number of values. The extra memory is a few variables, which is O(1), because the method keeps no copy of the window.

Worked example 1: the total of every window and the maximum

This program reads a list and prints the total of every window of length k, then the largest total. It is the full method in its plainest form.

The input has two numbers on the first line: n and k. The second line holds the n values. Save the program as main.py. Run it with python3 main.py, then type 6 3 and press Enter, then type 2 1 5 1 3 2 and press Enter.

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
 
# Build the first window: the sum of a[0] through a[k - 1].
window_sum = sum(a[:k])
best = window_sum
totals = [window_sum]
 
# Slide the window one step at a time.
# After each step the window covers a[i - k + 1] through a[i].
for i in range(k, n):
    window_sum += a[i]        # the value entering on the right
    window_sum -= a[i - k]    # the value leaving on the left
    totals.append(window_sum)
    best = max(best, window_sum)
 
print(" ".join(str(t) for t in totals))
print(f"max {best}")

Output:

8 7 9 6
max 9

Trace the loop. The first window total is 8, which is the first item in totals. The loop starts at i = 3. At that point the value entering is a[3], which is 1, and the value leaving is a[0], which is 2. The total becomes 8 + 1 - 2, which is 7. At i = 4 the value entering is a[4], which is 3, and the value leaving is a[1], which is 1. The total becomes 7 + 3 - 1, which is 9. At i = 5 the value entering is 2 and the value leaving is 5, so the total is 6. The largest total is 9, from the window at positions 2 to 4, which holds the values 5, 1, 3.

Notice that the loop starts at i = k, not at 0. If it started at 0, the leaving index i - k would be negative, and Python would read from the end of the list without warning. The mistakes section shows that case.

Python integers do not overflow, so the sums stay exact however large the values grow. The first window uses sum(a[:k]), a slice that copies k values and adds them. The copy is only k values, so it is cheap.

Worked example 2: where the best window starts

Often the question asks for more than the best total. It may ask where the best window starts, which values it holds, or its average. This program reads temperatures, finds the 3-value span with the largest total, and prints its start index, its values, and its average.

Type 8 3 and press Enter. Then type 3 -1 4 2 7 1 0 2 and press Enter.

n, k = map(int, input().split())
temps = [int(x) for x in input().split()]
 
window_sum = sum(temps[:k])
best_sum = window_sum
best_start = 0
for i in range(k, n):
    window_sum += temps[i]
    window_sum -= temps[i - k]
    start = i - k + 1
    # Strictly greater: on a tie, the earlier window is kept.
    if window_sum > best_sum:
        best_sum = window_sum
        best_start = start
 
best = temps[best_start:best_start + k]
print(f"window starts at index {best_start} covers {best}")
print(f"average {best_sum / k:.2f}")

Output:

window starts at index 2 covers [4, 2, 7]
average 4.33

There are six windows in this input. Their totals are 6, 5, 13, 10, 8 and 3, so the largest is 13, at start index 2. The program stores the start of each window in start and remembers it only when the total beats the best so far.

Three details matter here.

The comparison uses >, not >=. This decides which window wins a tie. With >, the earlier window stays. Decide this rule on purpose, because a question often says which answer it wants.

The slice temps[best_start:best_start + k] copies the window out of the list. The end index is not included, so the copy holds exactly k values. Using k as the length here is what keeps the copy the right size.

best_sum / k is a true division in Python. The / operator always gives a decimal number, so 13 divided by 3 is 4.333... and the format .2f shows two digits after the decimal point, as 4.33. The // operator is the one that drops the fraction, and it is not used here.

Worked example 3: a window over text

Windows work on text too. A string is a sequence of characters, and each character has a position, just like a list value. This example reads a word and a number k, then counts the windows of k characters that contain no repeated letter.

The hard part is knowing whether a window has a repeat. The program keeps the count of each character inside the window in a dict. A dict stores pairs of a key and a value, here a character and how many times it appears. The method counts.get(c, 0) returns that count, or 0 when the character is not in the dict yet.

The program also keeps repeated, the number of characters that appear two or more times in the window. A window has no repeated letter exactly when repeated is 0.

Type abcabcbb and press Enter. Then type 3 and press Enter.

text = input()
k = int(input())
 
counts = {}
repeated = 0   # characters that appear more than once in the window
good = 0       # full windows with no repeated character
 
for i, ch in enumerate(text):
    # Add the character entering on the right.
    before = counts.get(ch, 0)
    counts[ch] = before + 1
    if before == 1:
        repeated += 1      # it has just become a repeat
 
    # Remove the character leaving on the left, once the window is longer than k.
    if i >= k:
        out = text[i - k]
        now = counts[out] - 1
        if now == 0:
            del counts[out]
        else:
            counts[out] = now
            if now == 1:
                repeated -= 1  # it is no longer a repeat
 
    # Count this window if it is full and has no repeats.
    if i >= k - 1 and repeated == 0:
        good += 1
 
print(good)

Output:

4

The four good windows are abc, bca, cab and abc. The windows bcb and cbb each repeat a letter, so they are not counted.

The enumerate(text) loop gives both the position i and the character ch on each pass. That is the Python way to get an index and a value together, and it replaces text.charAt(i) in other languages.

Follow the first steps. At index 0 the program adds a and the window is not full yet. At index 1 it adds b. At index 2 it adds c, and the window abc is full with no repeats, so good becomes 1. At index 3 the program adds a. The letter a was already in the window once, so before is 1 and repeated becomes 1. Then the window must drop the letter at index 0, which is also a. Its count goes from 2 to 1, so repeated goes back to 0. The window bca is full with no repeats, and good becomes 2.

The same idea runs for any character set. Adding a character can create a repeat, and removing one can end a repeat. The program only updates repeated at those two moments, so it never looks at the whole window again.

Try a second input to test your reading. With abcdeabc and 4 the answer is 5.

Common mistakes

Starting the slide too early

A common first version starts the loop at index 0 and subtracts a[i - k] in the same step as adding. Here is that version.

Output:

i=0 sum=1
i=1 sum=-1
i=2 sum=2
i=3 sum=1
i=4 sum=3
i=5 sum=0

This program does not stop with an error. When i is 0, the index i - k is 0 - 3, which is -3. A negative index in Python counts from the end of the list, so a[-3] is the value 1, which is the third value from the end. The program subtracts 1 and keeps going. The totals are wrong from the first step on, and the printed numbers look like ordinary sums.

In a language like Java, the same index stops the program with an error. Python's negative indexes make this bug quieter, so check the loop start by hand. The fix is to build the first window before the slide, and start the slide at i = k, as the worked examples do.

Forgetting to remove the leaving value

Another mistake is to add the entering value and forget to subtract the leaving one. The program still runs and prints numbers, so the mistake is easy to miss. Here is the first worked example with the removal line deleted, run on the same input:

8 9 12 14
max 14

The totals keep climbing, because each step only adds. The true total of the second window is 7, but this program reports 9. Its maximum of 14 is not the sum of any window in the list. When a sliding total looks too large and keeps growing, check that every step removes a value.

Using a window longer than the list

The first window needs k values. If the list holds fewer than k values, the first loop reads past the end. Python raises an error for a positive index that is too big.

a = [4, 5]
k = 3
window_sum = 0
for i in range(k):
    window_sum += a[i]
print(window_sum)

Traceback (most recent call last):
  File "main.py", line 5, in <module>
    window_sum += a[i]
                  ~^^^
IndexError: list index out of range

Check k <= n before building the first window. If k is larger than n, there are no windows, so the right output is an answer that says so.

Getting the number of windows wrong

The last window starts at index n - k, so the loop that visits every start must run while start <= n - k, or equivalently while start + k <= n. A loop written as range(n - k) skips the last window. It is an off-by-one error: it is one step short. Count the windows on paper for a tiny list before you trust the loop bounds. For six values and k equal to 3, there must be four windows. The range(len(a) - k + 1) form in the slow way is the one to copy.

Using a big sum in other languages

Python integers never wrap around, so this mistake does not happen in Python. Other languages have a fixed-size integer type, and a sum past its limit becomes a wrong negative number with no error. Python needs no wider type for a running total, and the answer stays exact:

Output:

4000000000

Practice

Exercise 1: trace the totals

For the list [4, 0, 3, 2, 1] and k equal to 2, write the total of every window, in order.

Show the answer

The windows are 4, 0, 0, 3, 3, 2 and 2, 1. Their totals are 4, 3, 5 and 3. The output is 4 3 5 3.

Exercise 2: find the smallest window

Change the first worked example so it finds the smallest total of any window of length 3 in [2, 1, 5, 1, 3, 2]. Say which line changes.

Show the answer

Replace max with min in the last line of the loop. The starting value of best is the first window's total, which is a valid starting point for a minimum too. The smallest total is 6, from the window 1, 3, 2 at index 3.

Exercise 3: averages of windows

For the list [1, 2, 3, 4, 5] and k equal to 3, find the average of each window. Use / so the averages keep their fraction parts.

Show the answer

The totals are 6, 9 and 12. Dividing each by 3 gives the averages 2.0, 3.0 and 4.0. The / operator gives a decimal result, and // would drop the fraction.

Exercise 4: count the windows that reach a target

For the list [5, 5, 1, 9, 2] and k equal to 2, count the windows whose total is at least 10.

Show the answer

The windows are 5, 5, 5, 1, 1, 9 and 9, 2. Their totals are 10, 6, 10 and 11. Three of them reach 10, so the count is 3.

Exercise 5: explain the starting index

The first worked example starts its slide loop at i = k. Explain what goes wrong if it starts at i = k - 1 instead.

Show the answer

At i = k - 1, the program would add a[k - 1] a second time. That value is already the last value of the first window, so the total would be too large by that value. The leaving index would also be i - k, which is -1 when i is k - 1. In Python, -1 is not an error, it reads the last value of the list, so the mistake would stay hidden. The loop must start at i = k, so the first step adds the value after the first window and removes the value before it.

Summary

• A fixed-size window is a run of k neighbouring values, and it moves one position at a time.
• Build the first window's total with one sum, then for each new index add a[i] and subtract a[i - k].
• One pass costs O(n), and the work does not grow with k.
• Check that k is not larger than the list, and that the loop starts at i = k, because a negative index in Python does not raise an error.
• For text, a dict of counts lets the same add-and-remove idea answer questions about characters.