Fixed-size window
In one line
When a problem asks about every block of exactly k consecutive elements, keep one running answer and update it as the block slides by one, instead of recomputing each block from scratch.
What it is
A sliding window is a contiguous range of an array or string, described by two indices: where it starts and where it ends. In a fixed-size window the length never changes: it is always k elements long.
The window starts at positions 0 to k-1 and moves right one step at a time. Each step, exactly one element enters on the right and exactly one leaves on the left. If you can update your answer using only those two elements, every window costs O(1) and the whole scan costs O(n) instead of O(n * k).
Why interviewers ask
It is the gentlest introduction to the sliding window family and shows up as a warm-up or as the first step of a harder question. Interviewers want to see that you spot the repeated work in the brute force (re-adding k numbers for every window) and remove it, and that you handle the boundaries (k larger than n, the first full window) without off-by-one bugs.
How it works
- 1Build the first window: process elements 0 to k-1 and compute the window's state, for example their sum or a count of letters.
- 2Record the answer for this first window.
- 3For each new index right from k to n-1: add nums[right] to the state, and remove nums[right - k], the element that just fell out of the left side.
- 4Record the answer for the new window (positions right-k+1 to right).
- 5The state must be something you can update in O(1): sums, counts, a frequency array of 26 letters, or the number of items meeting a condition. If you need the maximum, see the monotonic deque page, because a maximum cannot simply be 'subtracted'.
Worked example · Largest sum of 3 consecutive numbers in [2, 1, 5, 1, 3, 2]
- k = 3. First window is indices 0 to 2: 2 + 1 + 5 = 8. Best so far = 8.
- right = 3: add nums[3] = 1, remove nums[0] = 2. Sum = 8 + 1 - 2 = 7 (window [1, 5, 1]). Best stays 8.
- right = 4: add nums[4] = 3, remove nums[1] = 1. Sum = 7 + 3 - 1 = 9 (window [5, 1, 3]). Best = 9.
- right = 5: add nums[5] = 2, remove nums[2] = 5. Sum = 9 + 2 - 5 = 6 (window [1, 3, 2]). Best stays 9.
- Answer: 9. We did 3 additions for the first window and 2 operations per slide, about 9 operations, versus 12 for the brute force. With n = 1,000,000 and k = 1,000 the gap is about 2 million versus 1 billion.
Picture it
Think of a train with k carriages passing a platform window. You do not count every passenger in all k carriages each time; you add the passengers in the carriage that just appeared and subtract the ones in the carriage that just left.
Reference code
def max_sum_window(nums, k):
"""Largest sum of any k consecutive numbers."""
if k <= 0 or k > len(nums):
raise ValueError("k must be between 1 and len(nums)")
window = sum(nums[:k]) # sum of the first window
best = window
for right in range(k, len(nums)):
# slide by one: add the new element, drop the one that fell out
window += nums[right] - nums[right - k]
best = max(best, window)
return best
def max_average(nums, k):
return max_sum_window(nums, k) / k # true division, not //
The first window is summed once, then each slide does one addition and one subtraction. Time O(n), extra space O(1). The guard makes the k > n case explicit instead of silently returning a wrong value.
Key patterns
Sum or average of every k-block
When: Max/min sum or average of k consecutive elements (for example LeetCode 643, Maximum Average Subarray I)
How: Running sum: add the entering element, subtract the leaving one, compare after each slide.
Count with a condition
When: Most vowels in any substring of length k, number of k-blocks with average at least a threshold
How: Keep a running count of elements meeting the condition; +1 if the entering element meets it, -1 if the leaving one did.
Anagram / permutation in a string
When: Find all anagrams of p in s, or check if s contains a permutation of p
How: Window of length len(p) with a 26-letter count array; compare it with p's counts after each slide (or track how many letters match).
Duplicate within distance k
When: Is there a repeated value at most k positions apart?
How: Keep a set of the last k elements; add the new one, remove the one k steps back, and check membership before adding.
Real-world use
Moving averages in finance apps
Stock charts on platforms like TradingView or Yahoo Finance show 50-day and 200-day moving averages. Each new trading day adds one closing price and drops the price from 50 days ago, which is exactly a fixed window sum divided by k.
Monitoring dashboards
Tools such as Grafana and Datadog show metrics like 'requests in the last 5 minutes' using fixed-length time windows, so a spike shows up quickly but one noisy second does not dominate the graph.
Rate limiting
API gateways limit clients to, say, 100 requests per minute. Sliding window counters, used for example in Cloudflare's rate limiting, estimate the count over the last fixed 60 seconds instead of resetting abruptly at each minute boundary.
Signal and sensor smoothing
Fitness trackers and IoT sensors smooth noisy readings with a moving average over the last k samples before deciding, for example, whether a step or a temperature spike really happened.
In a project
You build a server health dashboard that shows the average CPU usage over the last 60 readings (one per second) for 5,000 servers, refreshed every second.
- Keep, per server, a ring buffer of the last 60 readings and a running sum.
- On each new reading, add it to the sum, subtract the reading it overwrites in the ring buffer, and store the new one.
- Compute the average as sum / 60 (only once the first 60 readings exist; before that divide by the count so far).
- Raise an alert when the 60-second average stays above 90 percent, so short spikes do not page anyone.
Impact: Each update is O(1) instead of re-adding 60 numbers, so 5,000 servers cost about 10,000 operations per second instead of 300,000, and alerts fire on sustained load instead of on every one-second blip.
Trade-offs
Use it when
- The problem says 'subarray or substring of length k' or 'every k consecutive'
- The window state can be updated in O(1) when one element enters and one leaves (sums, counts, letter frequencies)
- Data arrives as a stream and you only need the last k items
Avoid it when
- The length is not fixed (shortest or longest subarray with a property): use a variable-size window
- The state cannot be undone cheaply, like a maximum or minimum: use a monotonic deque or a heap
- You need sums of many arbitrary ranges, not consecutive slides: prefix sums answer any range in O(1)
Cost: Time O(n) for all windows (versus O(n * k) brute force). Extra space O(1) for sums and counts, O(alphabet) for letter frequencies, O(k) if you store the window.
Common mistakes
- Recording an answer before the first window is full, for example comparing sums of 1 or 2 elements when k = 3.
- Removing the wrong element: the leaving element is nums[right - k], not nums[right - k + 1].
- Recomputing sum(nums[i:i+k]) in a loop, which is O(n * k) and is exactly what the technique is meant to avoid.
- Not handling k > len(nums) or k = 0, and using integer division (//) when the question asks for an average.
- Trying to slide a maximum by 'subtracting' the leaving element; maximums need a deque.
Interview questions
Quick revision
- Fixed window = always k elements; one enters, one leaves per step.
- Leaving element at step right is nums[right - k].
- Build the first window, record, then slide from right = k to n - 1.
- Time O(n), space O(1) for sums or counts.
- Anagram checks: 26-letter count array of window vs pattern.
- Max/min of each window cannot be subtracted: use a monotonic deque.
- Edge cases: k > n, k = 0, negative numbers (fine for fixed windows).
Check yourself
1. With nums = [4, 2, 1, 7, 8, 1] and k = 3, what is the largest window sum?
2. At step right in a fixed window of size k, which element leaves the window?
3. What is the time complexity of computing every window sum with the sliding technique?
4. Which quantity can NOT be maintained in O(1) per slide by just adding the new element and removing the old one?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.