Sliding Window · LC #643
Maximum Average Subarray I
Fixed-size sliding window: compute initial k-element sum, then slide one step at a time by adding the new element and removing the one that left. Pure intro to the sliding-window primitive.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Find the contiguous subarray of length `k` with the maximum average. Return the average as a double.
Sample I/O
Input: nums = [1,12,-5,-6,50,3], k = 4 Output: 12.75 (subarray [12,-5,-6,50]) Input: nums = [5], k = 1 Output: 5.0
Time: O(n) · Space: O(1)
Intuition
How to Think About It
Intuition
Recomputing the sum of every k-element window from scratch is O(nk). The key insight: adjacent windows share k-1 elements. Slide by subtracting the element that left and adding the one that entered - O(1) per step, O(n) total.
Core Concept
Sum the first k elements. For each subsequent position i (from k to n-1): `window += nums[i] - nums[i-k]`. Track `best = max(best, window)`. Return `best / k`.
When to use
Fixed-size window problems: maximum/minimum sum, average, product, or any aggregate over a window of fixed length k.
When NOT to use
Variable-size windows - use the shrink-when-invalid variant instead. When k > n - the problem is ill-defined.
Key Insights
What to Know Cold
- The sliding window avoids recomputing shared k-1 elements between adjacent windows.
- Track best SUM (integer), divide by k only once at the end to avoid floating point accumulation.
- The pattern `window += nums[i] - nums[i-k]` is the entire slide operation.
- This exact pattern extends to: max sum subarray of size k, count subarrays with exactly k distinct, etc.
- Contrast with variable-window problems (Longest Substring Without Repeating Chars) where you shrink based on a condition.
1 example
Worked Examples
Fixed-Size Sliding Window
nums=[1,12,-5,-6,50,3], k=4. Find maximum average of any 4-element window.
Initial window sum = 1+12-5-6 = 2. Slide: add 50, remove 1 → sum=51. Slide: add 3, remove 12 → sum=42. Best sum=51, average=51/4=12.75.
def findMaxAverage(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 / kThe purest fixed-window sliding-window template - once mastered, all fixed-k window problems reduce to this single pattern.