Fixed-Size Sliding Windows | AlgoDrill Interview Course

Given an integer array nums and an integer k with 1 ≤ k ≤ nums.length, return the largest average of any contiguous subarray containing exactly k values.

A direct solution adds all k values for every possible window. Neighboring windows overlap almost completely, so this repeats most of the same additions.

When a length-k window moves one position to the right, only two things change. The value at the old left edge leaves, and one new value enters at the right edge. Every value between them remains in the window.

Build the sum of the first k values once. After that, update each new window by subtracting the value that left and adding the value that entered. If right is the entering index, then right - k is the leaving index:

window_sum += nums[right]
window_sum -= nums[right - k]

Every window has the same length, so the window with the largest sum also has the largest average. Keep the best sum during the scan and divide by k only once at the end.

Slide a window of size k = 4

1 / 7

window_sum: 1
best_sum: not ready

Start with left and right at index 0. Add 1 to window_sum. The size-four window is not complete yet.

The animation builds the first window one value at a time. The code writes the same initialization more compactly with sum(nums[:k]).

Why can the next window sum be found by subtracting one value and adding one value?

1def find_max_average(nums: list[int], k: int) -> float:

2 window_sum = sum(nums[:k])

3 best_sum = window_sum

5 for right in range(k, len(nums)):

6 window_sum += nums[right]

7 window_sum -= nums[right - k]

8 best_sum = max(best_sum, window_sum)

10 return best_sum / k

Time: O(n)Space: O(k) in shown Python implementation

Building the first window takes O(k) time, and the remaining n - k slides each take constant time, so the total time is O(n). The sliding calculation stores only the current and best sums, but nums[:k] creates a temporary list of length k, so the shown Python implementation uses O(k) auxiliary space.

Given a lowercase string s and an integer k with 1 ≤ k ≤ s.length, return the largest number of vowels in any substring of length exactly k.

A fixed-size window can maintain any quantity that can be updated when one value leaves and another enters.

For the vowel problem, each character contributes either 1 or 0. A vowel contributes 1, while a consonant contributes 0. Adding those values gives the number of vowels in the current window.

When the window moves, subtract 1 if the leaving character is a vowel and add 1 if the entering character is a vowel. The boundaries move exactly as before, but the stored value now counts vowels instead of adding the characters themselves.

Count vowels in each length-three window

1 / 9

vowel_count: 1
best_count: not ready

Start with left and right at index 0. The window contains the vowel a, but it has not reached length 3.

In Python, character in "aeiou" produces True or False. Python treats those values as 1 and 0 when they are added to or subtracted from vowel_count.

1def max_vowels(s: str, k: int) -> int:

2 vowel_count = sum(ch in "aeiou" for ch in s[:k])

3 best_count = vowel_count

5 for right in range(k, len(s)):

6 vowel_count += s[right] in "aeiou"

7 vowel_count -= s[right - k] in "aeiou"

8 best_count = max(best_count, vowel_count)

10 return best_count

Time: O(n)Space: O(k) in shown Python implementation

Counting the first window takes O(k) time, and the remaining n - k slides each take constant time, so the total time is O(n). The sliding calculation stores only the current and best counts, but s[:k] creates a temporary string of length k, so the shown Python implementation uses O(k) auxiliary space.