Fixed-Size Windows
18 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Many problems ask about k items in a row. Recounting every block is slow. A sliding window moves one step at a time and fixes the answer with two small changes.
A window is a block of neighbours
Sliding window is a technique where you look at k neighbouring items at a time and move the block one step along the data, reusing what you already know instead of starting again.
Many questions ask about k items in a row: the best 7 days of sales, or 3 marks in a row. Each block of k neighbours is a window.
daily = [4, 2, 7, 1, 3, 6]k = 3for start in range(len(daily) - k + 1): print(start, daily[start:start + k])Example 1 · Brute force: sum every window again
sales = [4, 2, 7, 1, 3, 6]k = 3best = max(sum(sales[i:i + k]) for i in range(len(sales) - k + 1))print(best)13
What this code does
- Each window is sliced and added from scratch.
- This is correct and short. It costs O(n * k) time because every window adds k items.
A list of n items has n - k + 1 windows of size k. Two neighbouring windows share k - 1 items.
Slide instead of recounting
Adding all k items for every window repeats work. When the window moves one step, only one item enters and one item leaves. Change the sum by those two.
daily = [4, 2, 7, 1, 3, 6]k = 3total = sum(daily[:k])best = totalfor right in range(k, len(daily)): total += daily[right] - daily[right - k] best = max(best, total)print(best)Example 2 · Better: slide the sum and count the work
n, k = 1000, 100brute_adds = (n - k + 1) * kslide_adds = k + (n - k)print(brute_adds, slide_adds)90100 1000
What this code does
- Brute force adds k items for each of the n - k + 1 windows.
- Sliding adds the first window once, then one change per step.
- For n = 1000 and k = 100 that is 90100 against 1000 steps.
Example 3 · Moving average of every window
rates = [10, 12, 9, 15, 14, 11]k = 3total = sum(rates[:k])print(f"{total / k:.2f}")for right in range(k, len(rates)): total += rates[right] - rates[right - k] print(f"{total / k:.2f}")10.33 12.00 12.67 13.33
What this code does
- The running total is updated once per step.
- The first average is printed before the loop because the first window is built outside it.
- The f-string
:.2fshows two decimals.
Index right is the item that enters. Index right - k is the item that leaves. Each step is one add and one subtract, so the time is O(n) and the extra space is O(1).
Check the size first
If k is larger than the list, no window exists. A slice would quietly return a short block and give a wrong answer, so test the size before you slide.
def best_total(values, k): if k <= 0 or k > len(values): return None total = sum(values[:k]) best = total for right in range(k, len(values)): total += values[right] - values[right - k] best = max(best, total) return best
print(best_total([5, 1, 4], 2), best_total([5, 1], 3))Example 4 · A function that handles a short list
def best_total(values, k): if k <= 0 or k > len(values): return None total = sum(values[:k]) best = total for right in range(k, len(values)): total += values[right] - values[right - k] best = max(best, total) return best
print(best_total([2, 9, 1, 8], 2))print(best_total([2, 9], 5))print(best_total([-3, -1, -4, -2], 2))11 None -4
What this code does
Nonemeans "no window of that size".- Negative numbers work because best starts from the first real window, not from 0.
Return a clear value such as None when there is no window, and let the caller decide what to print.
Windows work on text too
A window can hold letters. To count vowels in every block of k letters, turn each letter into 1 or 0 and slide the total, just like numbers.
text = "placement"k = 4vowel = [1 if ch in "aeiou" else 0 for ch in text]total = sum(vowel[:k])best = totalfor right in range(k, len(text)): total += vowel[right] - vowel[right - k] best = max(best, total)print(best)Example 5 · Most vowels in any block of letters
text = "mentoring"k = 3vowel = [1 if ch in "aeiou" else 0 for ch in text]total = sum(vowel[:k])best = totalfor right in range(k, len(text)): total += vowel[right] - vowel[right - k] best = max(best, total)print(best)2
What this code does
- Each letter becomes 1 for a vowel and 0 otherwise.
- The window total is the number of vowels in k letters.
Example 6 · Count windows that reach a target
sales = [5, 3, 8, 2, 7, 4]k = 2target = 10total = sum(sales[:k])count = int(total >= target)for right in range(k, len(sales)): total += sales[right] - sales[right - k] count += total >= targetprint(count)3
What this code does
- A true comparison adds 1 to the count, because
Trueis the number 1 in Python. - The first window is counted before the loop.
Turning items into numbers first keeps the sliding code the same for every question.
Next step
Check your understanding
11 quick questions