Fixed and Bounded Windows
What is this?
A nurse checks a patient's average heart rate over every rolling 7-day span. She does not re-add seven numbers each morning: she adds today's reading and drops the one that just left the span. That is a fixed window: constant work per day, no matter how long the record.
The second half of this chapter is the harder question the same ward might ask: over how many stretches did the heart rate stay between 60 and 100, touching both limits? The window is no longer a fixed size, and re-scanning each candidate stretch is quadratic. The answer turns out to need only three remembered positions.
Fun fact: Count Subarrays With Fixed Bounds looks like it needs a nested loop and is solved by three integers. A subarray ending at
iis valid exactly when it starts after the last out-of-band element and early enough to include both aminKand amaxK, so counting the qualifying starts is a subtraction. It replaces enumeration with arithmetic on positions.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
In one line: when the window's length is fixed, roll the statistic. When the window is defined by a condition instead, stop thinking about windows and track the last position where each part of the condition was met or broken. The number of valid starts is then a subtraction.
1. The fixed roll
window = sum(nums[:k])
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # entrant in, leaver out
best = max(best, window)
Two things worth saying out loud in an interview. First, average and sum rank identically for a fixed k, so compare sums and divide once at the end, which avoids floating-point comparison entirely. Second, this works only because a sum can be undone by subtraction; had the problem asked for the window's maximum, this loop would be wrong and you would need a monotonic deque (see the rolling-hash and window-max chapter).
2. The bounded-extremes count
A subarray [start .. i] is valid when three things hold:
- it contains no element outside
[minK, maxK], - it contains at least one element equal to
minK, - it contains at least one element equal to
maxK.
Walk i forward keeping three positions: lastBad (the most recent index violating rule 1), lastMin and lastMax. A start position is valid exactly when it sits after lastBad and no later than both lastMin and lastMax. The number of such starts is:
count += max(0, min(lastMin, lastMax) - lastBad)
All three are initialised to -1, which makes the arithmetic work from the very first index with no special case.
3. A 30-second worked example
nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5.
The two valid subarrays are [1,3,5] and [1,3,5,2]. The 7 at index 4 poisons every start before it, and nothing after index 4 supplies a fresh minK, so the count stops growing. No subarray was ever enumerated.
4. Where you'll actually meet this
- Vital-sign and SLA monitoring. "How many stretches stayed inside the acceptable band?" is rule 1 plus the counting arithmetic above.
- Price collars. Finding periods where a price stayed inside a band, and the moment it broke out, is the
lastBadreset. - Moving averages. A rolling sum or average over a fixed window is usually implemented as a roll (add the entrant, drop the leaver) for exactly the reason above.
5. Problems in this chapter
Diet Plan Performance
Grade every fixed k-day window of calories against a lower and upper bound (+1, -1 or 0) and total the grades. The roll in its plainest form.
Pattern: fixed window, rolling sum. Target: O(n) time, O(1) space.
Count Subarrays With Fixed Bounds
Count subarrays whose minimum is exactly minK and maximum exactly maxK. Three tracked positions and one subtraction per index: no nested loop, and no window in the usual sense.
Pattern: last-position tracking + counting arithmetic. Target: O(n) time, O(1) space.
6. Common pitfalls
- Recomputing the window sum inside the loop. That is the difference between O(n) and O(nk), and it is easy to write by accident once the statistic is more than one variable.
- Comparing averages as floats. For fixed
k, compare sums and divide at the end. - Forgetting that
lastBadinvalidates everything before it. Every count after an out-of-band element must start strictly later than that index. - Initialising the three positions to
0. They must be-1, or the first index is counted as though a valid start already existed. - Dropping the
max(0, …)clamp. Whenmin(lastMin, lastMax)falls beforelastBad, the subtraction goes negative and silently eats earlier counts. - Special-casing
minK == maxK. It needs none: both positions update on the same element and the arithmetic still holds.
7. Key takeaways
- A fixed window rolls: add the entrant, remove the leaver, O(1) per step.
- Only reversible statistics can roll. Sums yes, maximums no.
- When the window is defined by a condition, track positions rather than contents. Three integers replace an inner loop.
- Valid starts form a range, so counting them is a subtraction rather than an enumeration.
- Initialise boundary positions to
-1and the first-index case handles itself. - Why interviewers like it: the fixed roll is a warm-up; the bounded-extremes problem tests whether you can restate a condition about subarrays as constraints on their start positions, which is a genuinely different way of seeing it.
Order: Diet Plan Performance → Count Subarrays With Fixed Bounds.
Count Subarrays With Fixed Bounds
Core idea: A subarray counts only if its minimum is exactly
minKand its maximum is exactlymaxK. Scan left to right and keep three "last seen" positions: the last index of aminK, the last index of amaxK, and the last index of any out-of-range value (< minKor> maxK). For each right endi, a valid subarray must start after the last bad element and at or before both the lastminKand the lastmaxK. That gives a one-line count,max(0, min(lastMin, lastMax) - badIdx), and summing it over alliis a single O(n) pass.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson