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 subtracts the one from eight days ago. 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 entirely 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 i is valid exactly when it starts after the last out-of-band element and early enough to include both a minK and a maxK — so counting the qualifying starts is a subtraction. It is an unusually pure example of replacing enumeration with arithmetic on positions.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: when the window's length is fixed, roll the statistic. When the window is defined by a condition instead, stop thinking about windows and start tracking 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 — it sidesteps 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 deque.

2. The bounded-extremes count

A subarray [start .. i] is valid when three things hold:

1. it contains no element outside [minK, maxK],
2. it contains at least one element equal to minK,
3. 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.

i  val  lastBad  lastMin  lastMax   min(lastMin,lastMax) - lastBad   count
0    1     -1       0       -1       min(0,-1) = -1 → -1 - (-1) = 0     0
1    3     -1       0       -1       -1 - (-1) = 0                      0
2    5     -1       0        2       min(0,2) = 0 → 0 - (-1) = 1        1
3    2     -1       0        2       0 - (-1) = 1                       2
4    7      4       0        2       0 - 4 = -4 → clamped to 0          2
5    5      4       0        5       0 - 4 = -4 → clamped to 0          2
                                                            answer = 2

The two valid subarrays are [1,3,5] and [1,3,5,2]. Notice how 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.
• Manufacturing quality control. Statistical process control asks precisely this: count runs that stayed within tolerance while touching both control limits.
• Financial compliance. Detecting periods where a price stayed inside a collar — and the moment it broke out — is the lastBad reset.
• Time-series databases. Moving averages over fixed windows are the base case in every one of them, implemented as a roll for exactly the reason above.
• Audio and sensor processing. Fixed-size frames with rolling energy calculations underpin most real-time signal pipelines.

5. Problems in this chapter

▶ Diet Plan Performance

Score a fixed k-day window of calories against a lower and upper bound, totalling points across all windows. 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 lastBad invalidates 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. When min(lastMin, lastMax) falls before lastBad, 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

1. A fixed window rolls — add the entrant, remove the leaver, O(1) per step.
2. Only reversible statistics can roll. Sums yes, maximums no.
3. When the window is defined by a condition, track positions rather than contents. Three integers replace an inner loop.
4. Valid starts form a range, so counting them is a subtraction rather than an enumeration.
5. Initialise boundary positions to -1 and the first-index case handles itself.
6. 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.