A metrics job walks a day’s request-latency series. For every index i it wants the sum of the next k samples — rolling error counts, last-minute totals, “units shipped in the last 60 events.” The first version nested a loop: start at i, add k slots, store the total, then start over at i + 1. The same shape shows up as “longest stretch of SKU codes with at most k distinct values,” scanned by restarting j from i on every outer step. Forty rows pass the unit test. A few million do not.
A sliding window is a contiguous range that grows on the right and shrinks on the left so each element is added and removed at most once. You keep an aggregate of [left, right] — a sum, a frequency map, a count of distinct SKUs — and you update it when the ends move. You do not rescan the interior.
This is a search-and-scan procedure on a layout you already have, usually an array. Families, glossary, and the catalog live on the Algorithms Roadmap. This post is the window.
The scan that restarts
Nobody wrote the nested version badly on purpose. The spec is “every k-length slice.” A slice is a contiguous range. The obvious code names the range with two loops:
int[] sumsFromScratch(int[] latencies, int k) {
int n = latencies.length;
int[] out = new int[n - k + 1];
for (int i = 0; i + k <= n; i++) {
int sum = 0;
for (int j = 0; j < k; j++) {
sum += latencies[i + j];
}
out[i] = sum;
}
return out;
}Adjacent answers share k - 1 terms. The inner loop pays for those terms again. That is O(nk). The unique-count cousin is the same bill: for each i, walk j forward until the distinct-SKU set breaks, then throw the set away and start at i + 1.
The layout is already right — a contiguous array makes latencies[i] free. The procedure is wrong. You are treating each window as a fresh range instead of a range that moved by one.
The invariant: add right, drop left
Two indices, both moving only forward.
rightis the next element that wants in. You adda[right]to the aggregate, then advanceright.leftis the oldest element still in. When the window is invalid (too long, too many distinct keys, sum too large), you dropa[left]from the aggregate, then advanceleft.
Every index is added once and dropped at most once. left never walks backward. right never walks backward. The interior is not visited again. That is the whole algorithm. The aggregate is whatever the job needs — an int sum, a Map of frequencies, a running count of unique keys — as long as you can apply “include this” and “exclude this” in cheap time.
Note: “Window” here is a pair of indices on the original array, not a copied sub-array. Copying [left..right] on every step is the nested scan in a new costume.
Two shapes share that invariant.
| Shape | What stays true | Typical job |
|---|---|---|
| Fixed | right - left + 1 == k after each step | Running sum / average of the last k |
| Variable | Grow until invalid, shrink until valid | Longest / shortest range that meets a constraint |
Fixed is variable with a length constraint you restore on every step: add one on the right, drop one on the left. Variable is the same verbs with a predicate instead of a constant k.
Fixed window: last k, running sum
Build the first window of length k in a single pass. After that, each new right endpoint costs two updates: add the new sample, drop the sample that just aged out.
int[] sumsOfLastK(int[] a, int k) {
int n = a.length;
int[] out = new int[n - k + 1];
int sum = 0;
for (int i = 0; i < k; i++) {
sum += a[i];
}
out[0] = sum;
for (int i = k; i < n; i++) {
sum += a[i];
sum -= a[i - k];
out[i - k + 1] = sum;
}
return out;
}i - k is the left endpoint of the window that just became too long. You do not name left as a separate variable because the length is constant: left is always right - k + 1. Same invariant, shorter bookkeeping.
A five-sample series, k = 3:
a = [4, 1, 7, 2, 3] k = 3
build [4, 1, 7] sum = 12 out[0] = 12
add 2, drop 4 sum = 10 window [1, 7, 2]
add 3, drop 1 sum = 12 window [7, 2, 3]
out = [12, 10, 12]The second window did not re-add 1 and 7. It inherited them. That is the O(n) claim in one picture: two arithmetic ops per step after the first window, not k additions.
Note: If k > n, there is no legal window. Guard that at the call site. An empty a is the same story: zero windows, not a special scan.
Unique-count over a fixed length is the same skeleton with a frequency map instead of a sum: increment the incoming key, decrement the outgoing key, remove the key if its count hits zero, then read map.size(). Still one add and one drop per step.
Variable window: grow until invalid, shrink until valid
The length is not given. The constraint is. Classic shape: longest contiguous run with at most k distinct SKUs. right always advances. left advances only while the map of live keys is too large.
int longestAtMostKDistinct(String[] skus, int k) {
Map<String, Integer> freq = new HashMap<>();
int left = 0;
int best = 0;
for (int right = 0; right < skus.length; right++) {
freq.merge(skus[right], 1, Integer::sum);
while (freq.size() > k) {
String drop = skus[left];
int remaining = freq.merge(drop, -1, Integer::sum);
if (remaining == 0) {
freq.remove(drop);
}
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}Grow is the for. Shrink is the while. Validity is freq.size() <= k. You record best only after the window is valid again — otherwise you would credit an illegal range.
Walk A B A C C B with k = 2:
skus: 0:A 1:B 2:A 3:C 4:C 5:B k = 2
right 0 add A {A:1} valid len 1 best 1
right 1 add B {A:1, B:1} valid len 2 best 2
right 2 add A {A:2, B:1} valid len 3 best 3
right 3 add C {A:2, B:1, C:1} invalid (3 keys)
drop A {A:1, B:1, C:1} still 3
drop B {A:1, C:1} valid len 2 window [2..3]
right 4 add C {A:1, C:2} valid len 3 best 3
right 5 add B {A:1, C:2, B:1} invalid
drop A {C:2, B:1} valid len 3 window [3..5]
best = 3 (ABA at the start, or CCB at the end)left moved three times in the whole pass (0, then 1, then 2). right moved six times. No index was added twice. That is why the while does not make the algorithm quadratic: every drop is paid once, globally, not once per right.
The shortest-window twin flips when you record the answer. Grow until the constraint holds (sum at least target, at least k distinct, a required set covered), then shrink while it still holds, and the length after the last successful shrink is a candidate minimum. Same two verbs. Different moment of measurement.
Note: Shrink-until-valid needs a monotonic constraint: once [left, right] is invalid, a longer window on the left would have been invalid too, so you never put left back. “At most k distinct” is monotonic. “Sum equals target” on an array that contains negatives is not — a later add can make a previously oversized sum legal again. That job is not this procedure.
Not opposite-end two pointers, not a rate-limit window
Sliding window uses two pointers. They are not the opposite-end pair.
Opposite-end two pointers start at 0 and n - 1 and walk toward each other — pair-sum on a sorted array, a palindrome check. One end increases, the other decreases, and they meet. A sliding window’s left and right both increase. The range is a contiguous interior that crawls forward. If you find yourself decrementing right, you left this procedure.
A rate-limit “sliding window” is a time-horizon policy on when a request is allowed — token bucket, leaky bucket, and the request-count window that shares the name — not this scan of a contiguous array.
Complexity is O(n)
Time is linear in the length of the array.
Each index is visited by right once. Each index is visited by left at most once. Updates to the aggregate are O(1) for a sum or count, and O(1) amortized for a HashMap increment/decrement. Multiply those out and you get O(n), not O(nk).
Space is the aggregate. A running sum is O(1) extra. A frequency map is O(u) where u is the number of distinct keys that can sit in the window at once — at most n, and for “at most k distinct” at most k + 1 before you shrink.
The inner while is not a nested O(n) per step. It is the drop-left loop. Its total iterations across the whole pass are at most n.
Window maximum sits on a deque, not on this loop alone
The running-sum window is enough when the aggregate has a cheap inverse: add x, later subtract x. A maximum does not: dropping the current max does not tell you the second-max unless you kept candidates.
Window-maximum algorithms usually keep a deque of candidate indices (decreasing values, drop from the back when a new value dominates, drop from the front when an index ages out of the window). Same add-right / drop-left range; extra invariant on the deque. The layout job is cheap ends. This post does not teach that second algorithm — only that the deque is the structure those candidates live in, not a second nested scan of the window.
When not to use
Skip a sliding window when:
- The answer is not a contiguous range — any
kitems, a subsequence, “pick slots that need not sit together.” That is a different procedure (often DP or a subsequence post later in the catalog). The window’s whole point is the slice[left, right]. - Random access inside the window is the hot path, and you do not have the original array (or a deque of ends). Two indices on an array already make
a[i]free forleft <= i <= right. If you copied the live slice into a list and nowget(i)the middle on every event, you rebuilt a mini-array you did not need — or you need a real random-access layout, not a window aggregate. - The aggregate has no cheap include/exclude. “XOR of the window” does. “Median of the window” does not, unless you maintain extra structure. “Maximum of the window” without a deque of candidates falls back to rescanning, which is the restarting job this post retired.
A window is the wrong name for “I will sort each slice” or “I will hash the whole slice from scratch.” Those may still be correct algorithms. They are not this one.
Cheat sheet
Job: aggregate of a contiguous range that moves
Invariant: add a[right], drop a[left]; each index at most once
Fixed: length k — add one, drop one (running sum / unique-count)
Variable: grow until invalid, shrink until valid (longest / shortest)
Not: opposite-end two pointers; not a rate-limit time window
Time: O(n) — left and right each walk the array once
Space: O(1) sum/count; O(u) for a frequency map
Skip: non-contiguous; interior get(i) as the hot path; max without a dequeDo:
- Keep the aggregate on the array with two indices. Update it at the ends.
- Shrink only while the window is invalid (or, for a minimum, while it remains valid).
- Name the constraint first — length
k, at mostkdistinct, sum at leastt— then pick fixed vs variable.
Don’t:
- Rescan
kslots from eachiwhen adjacent windows sharek - 1terms. - Decrement
right, or treat this as the opposite-end pair-sum loop. - Copy
[left..right]into a new array on every step and call it a window.
Wrap-up
A sliding window is a contiguous range with an add-right / drop-left invariant. Fixed length is a running aggregate of the last k. Variable length grows until the constraint breaks and shrinks until it holds. Each element enters and leaves at most once, so the pass is O(n) on an array you already had.
Use it when the hot job is an aggregate of a slice that crawls forward. Use something else when the items need not be contiguous, when the hot path is an interior index, or when the aggregate has no cheap inverse. The catalog of those other procedures — and the glossary this post did not repeat — is the Algorithms Roadmap.