Why is a rolling sum over every length-k window O(n) work while recomputing each window costs O(n·k)?
answer
- How much do neighbouring windows overlap?
- Only the two ends differ
- One value enters, one leaves
- Constant work per slide, n slides
- Recomputation redoes k-1 additions already done
basics
~20 sAdjacent windows differ by exactly two elements, so a rolling sum adds the entering value and subtracts the leaving one in constant time instead of re-adding all k. Across n slides that is O(n) total work rather than O(n·k).
solid answer
~40 sTwo neighbouring windows of the same size share k-1 elements, so recomputing the whole sum for each one redoes k-1 additions you already performed. Keep one accumulator instead: on each step add the value entering on the right and subtract the value falling off the left, which is O(1) per slide and O(n) over the whole pass. For a vibration monitor emitting a 60-sample mean per reading, that is one add and one subtract per reading instead of sixty. One honest caveat interviewers like to hear: when k is a fixed constant such as 60, recomputation is still O(n) asymptotically — it just does about 60x the work. The bound only separates into O(n·k) versus O(n) when k grows with the input, for example a window covering a fixed fraction of the stream.
code
pseudocode · 10 linesk = 60
sum = 0
for i in 0..length(a)-1:
sum = sum + a[i] // element entering on the right
if i >= k:
sum = sum - a[i - k] // element that just fell off the left
if i >= k - 1:
// invariant: sum == a[i-k+1] + ... + a[i]
emit(sum / k)
...go deeper
Be ready to say, in one breath, that neighbouring windows differ by exactly two elements and to write the add-entering / subtract-leaving loop without hesitating over where the first result comes out.
Explain the cost accounting element by element — each value is added once and subtracted once across the whole pass — and state the loop invariant that pins which k elements the accumulator currently holds.
Show that you notice when k is a constant and the win is a constant factor rather than an asymptotic one, and that you check whether the aggregate is invertible before promising an O(1) update.
Own the framing question: is the window fixed at all? Argue about who chooses k, what the memory floor of O(k) retained samples means on constrained hardware, and when an approximation is the better engineering call.
## The setup A fixed-size sliding window is the simplest member of the sliding-window family: the window length k never changes, it moves one position at a time, and you want some aggregate — usually a sum, a mean, or a count — for every position it occupies. A vibration monitor that raises an alarm when the mean of the last 60 samples crosses a threshold is exactly this shape: for each new reading, produce the mean of the 60 readings ending there. ## What actually changes between neighbouring windows The whole pattern rests on one observation. The window covering positions `[i-k+1 .. i]` and the window covering `[i-k+2 .. i+1]` overlap in `k-1` positions. Only two elements differ: the one that *enters* on the right and the one that *leaves* on the left. Everything in between is identical, and any aggregate that can be *undone* — sum, count, sum of squares, exclusive-or — can therefore be transported from one window to the next with two constant-time operations rather than k. The naive version recomputes: ``` for each start position s: total = 0 for j in s..s+k-1: total = total + a[j] ``` There are about `n - k + 1` windows and each inner loop runs k times, so the cost is `O((n-k+1)·k)`, bounded by `O(n·k)`. The rolling version touches every element exactly twice over the whole run — once when it enters the accumulator, once when it leaves — so the total is `O(n)` with `O(1)` extra state for the sum itself. | Approach | Per slide | Whole pass | Extra state | |---|---|---|---| | Recompute each window | O(k) | O(n·k) | O(1) | | Rolling add/remove | O(1) | O(n) | O(1) for the sum, plus whatever you need to know the leaving value | ## The constant-k caveat that separates a careful answer Big-O hides constants, and k is often a constant. With k pinned at 60, `O(n·60)` **is** `O(n)` — the two approaches are in the same complexity class, and the rolling version's win is a 60x constant factor, not an asymptotic one. That is still the difference between a monitor that keeps up with a 10 kHz sensor and one that does not, but it is a constant-factor argument and you should name it as such. The asymptotic separation is real only when k varies with the input: a window of size `n/2`, or a k supplied by the caller and allowed to grow, makes the recompute genuinely quadratic-ish while the rolling version stays linear. Candidates who assert "O(n·k) versus O(n)" without noticing that k may be constant are stating the right conclusion from a shaky premise; candidates who say "same class, 60x the work, and it separates the moment k scales" are demonstrating that they understand what the notation quantifies over. ## The boundary, which is where the bugs live A one-pass formulation folds the window fill-up into the same loop: - add `a[i]` unconditionally; - once `i >= k`, subtract `a[i-k]`, because that element has now fallen out; - once `i >= k-1`, the accumulator holds exactly k elements, so emit a result. The two thresholds differ by one and swapping them is the classic off-by-one here: emitting at `i >= k` silently drops the first legitimate window, and emitting from `i == 0` reports means over partially filled windows that look plausible and are wrong. State the invariant out loud when you write the loop — *after the update at step i, the accumulator equals the sum of `a[i-k+1 .. i]` whenever `i >= k-1`* — and the boundaries follow from it rather than from trial and error. ## Where the trick stops working The rolling update needs the aggregate to be invertible: you must be able to remove the leaving element's contribution knowing only that element and the current aggregate. Sums, counts and exclusive-ors qualify. A median does not — knowing the current median and the departing value tells you nothing about the new median, so a rolling median needs an ordered structure over the k live values and costs O(log k) per slide rather than O(1). Recognising which aggregates are invertible is what lets you predict, before writing anything, whether a fixed window buys you a linear pass or not. ## The storage nobody mentions The *sum* is one number, but subtracting the leaving element means you must still be able to name it. If the readings live in an array you index backwards by k and store nothing extra; in a streaming setting where readings arrive one at a time and are discarded, you must retain the last k values in a circular buffer, so the real space cost of a fixed window is O(k), independent of n. That is the property that makes fixed windows usable on unbounded streams: memory is set by the window, never by how long the stream has been running.
- In that loop, why does the first result appear at index k-1 rather than at index k?After the update at step i the accumulator holds `a[i-k+1 .. i]`, which is exactly k elements as soon as `i == k-1`. Emitting from `i == k` skips the first legitimate window entirely; emitting before `i == k-1` reports an average over a partially filled window, which is wrong but looks plausible in the output.
- Does the same add-and-remove trick give you a rolling median for free?No. The trick needs an invertible aggregate — one whose leaving element's contribution can be subtracted out. A median is not: the current median plus the departing value tells you nothing about the next median. A rolling median needs an ordered structure over the k live values, costing O(log k) per slide instead of O(1).
- What is the space cost of a fixed-size window on a stream of unknown length?O(k), never O(n). The accumulator is one number, but to subtract the leaving value you must still be able to name it, so you retain the last k readings in a circular buffer. Memory is set by the window size, not by how long the stream has been running — which is why this pattern survives unbounded input.
Like sliding a picture frame along a mural: you do not re-examine the whole strip of wall inside the frame, you only look at the sliver that just appeared and the sliver that just vanished.
saying these in an interview costs you the question
- Says k work per window is fine because k is small
- Claims the rolling version changes the class even for constant k
- Thinks every window aggregate can be rolled incrementally
- Emits a result before the window is full
- Forgets that the leaving value must still be retrievable