DSA · Arrays · Fixed and variable windows

Slide the window, keep the sum

Q: When the right edge is at index r, which index leaves?

Index r − k . The new window covers r−k+1 through r , so the position immediately before it is what fell out. Using r−k+1 , or using left after you have already incremented it, is the standard off-by-one.

Q: The variable version has a while loop inside a for loop. Is that O(n²)?

No, it is O(n) . Every pass of the while body advances left by exactly one, and left only ever increases and can never exceed n — so the body runs at most n times across the entire loop, not n times per iteration. Amortised, every element enters the window once and leaves at most once, which is 2n operations.

Two neighbouring windows share almost every element. Let one element in, let one element out, repair the running total — and a whole family of subarray questions drops from O(n·k) to O(n).

Step through both versions on 2 1 5 1 3 →

Recompute each window · 9 operations

→

Slide the window · 7 operations

01 The idea

The overlap is the whole trick

A window is a block of consecutive elements — a subarray you treat as one unit. A surprising number of questions are really window questions: the largest sum of any three in a row, the longest stretch that stays under a limit, the longest substring with no repeated letter.

The obvious way is to build every window from scratch. Over 2 1 5 1 3 with a width of 3 that is 3 windows and 9 additions. Now look at what two neighbouring windows share. Indices 0–2 hold 2, 1, 5 and indices 1–3 hold 1, 5, 1. The 1 and the 5 are in both. Adding them again is work you already did.

Move the right edge to let one element in, move the left edge to let one element out, and repair the running total using only those two elements. Never add up the middle again.

WindowA block of consecutive positions held by two indices: a left edge and a right edge. Everything between them is inside.

Running totalOne number that always holds the sum of whatever is currently inside the window. You repair it; you never rebuild it.

Fixed vs variableA fixed window keeps the same width k the whole way. A variable window grows on the right and shrinks on the left until a condition is satisfied.

02 Hand trace

k = 3 over 2 1 5 1 3

Find the largest sum of any three neighbouring numbers in 2 1 5 1 3. Five elements and a width of three give 3 windows. Rose boxes are inside the window right now. Watch the sum, not the elements.

build 0–2215132+1+5 = 8 → best 8

slide to 1–3215138 +1 −2 = 7 → 7 < 8, keep 8

slide to 2–4215137 +3 −1 = 9 → new best 9

result21513best window sum = 9 at 2–4

Three windows, but only the first one was added up in full. The other two cost one addition and one subtraction each — 7 arithmetic operations instead of 9. That gap looks small on five numbers, so scale it: on a list of 100 with a width of 50, rebuilding costs 51 windows × 50 = 2550 additions, while sliding costs 50 + 2 × 50 = 150 operations. That is the worst case for the naive version — recomputing hurts most at k = n/2, and eases off again as k approaches n, because there are barely any windows left to build. The code in section 03 is what removes the gap entirely.

03 Naive vs improved

The same answer, two very different costs

Both versions return the largest sum of k consecutive numbers. The left one is what you write first. The right one is the same idea with the inner loop deleted.

Recompute every window

best = -infinityfor start = 0 to n - k:    sum = 0    for t = start to start + k - 1:        sum = sum + nums[t]    best = max(best, sum)return best

Slide the window

sum = 0for t = 0 to k - 1:    sum = sum + nums[t]best = sumfor r = k to n - 1:    sum = sum + nums[r] - nums[r - k]    best = max(best, sum)return best

The inner loop is gone. It was re-adding the k−1 elements the previous window had already counted — the 1 and the 5 you saw shared in the trace. Deleting it is the entire optimisation; everything else is bookkeeping to make the deletion safe.

The first window is paid for by hand. There is nothing to slide from yet, so lines 2–3 spend the full k additions once. Every window after that costs two, no matter how wide k is.

nums[r - k] is the element leaving. When the right edge sits at r, the window covers r-k+1 through r, so the position immediately before it — r-k — is what just fell out. Getting this index wrong by one is the classic sliding-window bug.

When the width is not given

Not every window has a fixed size. Ask instead: how long can the window get while its sum stays at or under a target? The right edge still moves forward every iteration; the left edge only catches up when the rule breaks.

left = 0;  sum = 0;  best = 0for right = 0 to n - 1:    sum = sum + nums[right]              # let one in    while sum > target:                  # too big? let some out        sum = sum - nums[left]        left = left + 1    best = max(best, right - left + 1)return best

Run it on the same list with target 7. Sums go 2, 3, then 8 — too big, so drop the 2 and the window becomes 1–2 with sum 6. Add the next 1 and the window 1–3 sums to exactly 7, width 3. Add the 3 and the sum hits 10, so the left edge drops the 1 and then the 5. The answer is 3, and the winning window is 1 5 1.

The while loop does not make it quadratic. left only ever increases, and every pass of the while body increases it by exactly one — so it can fire at most n times over the whole run, not n times per iteration. Each element enters the window once and leaves at most once: 2n operations, which is O(n).

This shape needs non-negative values. Shrinking from the left is only guaranteed to lower the sum when every element is 0 or more. With negatives, dropping an element can raise the sum, and the window stops behaving — that is when you switch to prefix sums: a hash map for exact-sum questions, a sorted or monotonic structure for at-most questions.

05 Cheat sheet

The numbers worth carrying into the room

Case	Cost	Why
Fixed window, recomputed	`O(n · k)`	The inner loop re-adds the k−1 elements the last window already counted. Exact cost k(n−k+1), which peaks at k = n/2 — that is where it is genuinely quadratic.
Fixed window, slid	`O(n)`	k additions to build the first window, then exactly 2 operations per slide: k + 2(n−k) = 2n − k in total.
Variable window, non-negative values	`O(n)`	Right edge moves n times, left edge moves at most n times in total. Amortised linear.
Extra space, running sum	`O(1)`	Two indices and one total. The array itself is only read, never copied.
Extra space, frequency map	`O(k)`	Needed when the summary is a character or value count rather than a number.
Number of windows of width k	`n − k + 1`	3 windows for n = 5, k = 3. Zero windows when k > n — guard that input.

Contiguous onlyA window is a subarray, never a subsequence. If the problem lets you skip elements, this is the wrong tool.

One pass, both edges forwardNeither edge ever moves backwards, which is the reason the total work stays linear.

Needs an O(1) repairA sum, a count, a frequency map. If the summary costs O(k) to update anyway, sliding saves nothing.

06 Where & why

Knowing when the window is the right shape

Sliding window is not a data structure and not a clever trick. It is what you reach for when the answer lives in a contiguous block and that block's summary can be repaired in constant time as the edges move. Everything else is a different pattern wearing a similar name.

Reach for it when…

The answer is a subarray or substringThe elements must sit next to each other — "max sum of k in a row", "longest substring without repeats".

The width is fixed and givenk is in the question. Build one window, then slide n−k times and you are done.

The condition is monotoneGrowing the window can only push the measure one way, shrinking only the other. That is what makes a single left pointer enough.

The summary repairs in O(1)You can update the sum, count or map from just the entering and leaving element without touching the middle.

Use something else when…

Situation	Better choice	Why
Best subarray sum, values may be negative	Kadane's algorithm	Shrinking from the left can raise the sum, so the shrink rule breaks. Kadane handles mixed signs in one O(n) pass.
Many range-sum queries on a fixed array	Prefix sum array	Build once in O(n), then every range answers in O(1). Re-sliding per query would be O(n) each time.
The chosen elements need not be adjacent	Sorting, DP or a heap	A window can only ever look at consecutive positions, so it cannot express "pick any k".
You need the maximum inside every window, not the sum	Monotonic deque	A maximum cannot be repaired by subtraction — the leaving element may be the maximum, and nothing tells you the next best.

In an interview the phrase "contiguous subarray" or "substring" is the signal. Before you write a line, say the window out loud: what enters, what leaves, and what the running total must be repaired to. If you cannot answer all three in one sentence, it is not a window problem.

07 Interview questions

Eleven answers you should be able to speak

Roughly the order an interviewer escalates: what it is, what it costs, why it costs that, where it breaks, and whether you would really use it.

What is the sliding window technique?

It keeps a block of consecutive elements plus a running summary of that block. When the block moves, you repair the summary using only the element that entered and the element that left, instead of scanning the block again. That turns an O(n·k) scan into O(n).

Why is the fixed-size version O(n) and not O(n·k)?

Because after the first window every window costs exactly two operations, one addition and one subtraction. The first window costs k, then there are n−k slides at 2 each, so the total is k + 2(n−k) = 2n − k — at most 2n however large k gets. The per-slide cost is fixed at 2, so k never enters the complexity.

Walk me through max sum of k = 3 on 2 1 5 1 3.

The first window is 2+1+5 = 8, so best is 8. Slide once: nums[3] = 1 enters and nums[0] = 2 leaves, so the sum becomes 7 — smaller, keep 8. Slide again: nums[4] = 3 enters and nums[1] = 1 leaves, so the sum becomes 9, which is a new best. The answer is 9, from indices 2 to 4.

When the right edge is at index r, which index leaves?

Index r − k. The new window covers r−k+1 through r, so the position immediately before it is what fell out. Using r−k+1, or using left after you have already incremented it, is the standard off-by-one.

Fixed window versus variable window — what actually changes?

In a fixed window both edges move together and the width never changes, so there is no inner loop at all. In a variable window the right edge advances every iteration and the left edge advances only while a condition is violated, which needs a while loop. Fixed answers "what is the best window of width k"; variable answers "how wide can a legal window get".

The variable version has a while loop inside a for loop. Is that O(n²)?

No, it is O(n). Every pass of the while body advances left by exactly one, and left only ever increases and can never exceed n — so the body runs at most n times across the entire loop, not n times per iteration. Amortised, every element enters the window once and leaves at most once, which is 2n operations.

Why does the technique break with negative numbers?

The shrink step assumes that removing an element from the left lowers the sum. With negatives, dropping a −4 raises it, so the loop either shrinks forever or stops too early and you miss the answer. For "longest subarray with sum at most target" over mixed signs you switch to prefix sums with a hash map or an ordered structure.

How much extra space does it need?

O(1) for a plain running sum: two indices and one total, with the array only read. It becomes O(k), or O(distinct values), once the summary is a frequency map — for example in longest substring without repeating characters.

Sliding window versus two pointers — are they the same thing?

Sliding window is a special case of two pointers where both pointers move in the same direction and the region between them is the answer. General two-pointer problems often walk inwards from both ends, as in two-sum on a sorted array, and keep no summary of the region between. If you are maintaining something about the middle, it is a window.

How many windows of width k are there in an array of length n?

n − k + 1 when k <= n, and zero otherwise. For n = 5 and k = 3 that is 3 windows, which matches the trace. Guard the k > n case explicitly — it is the input most submissions crash on.

When would you actually use this outside an interview?

Any time you summarise a moving range: a rolling average on a metrics dashboard, rate limiting by requests in the last minute, smoothing a chart, or a checksum over a shifting block of bytes. Unlike most O(n²) teaching algorithms, this pattern goes into production unchanged.

08 Practice problems

Six problems, in the order you should attempt them

Every one is solvable with only what this page taught. Work down the list — the last one is where the pattern runs out and something bigger takes over.

Maximum sum of k in a row

Easy

Given an array of positive integers and a width k, return the largest sum of any k consecutive elements.

Follow-up

Count every add and subtract your solution performs and check the total is k + 2(n−k). If it is higher, an inner loop survived somewhere.

Show the hint

Build the sum for indices 0 to k−1 before the main loop starts, so the loop only ever handles r = k onward.

Rolling averages

Easy

Given an array and a width k, return the average of every window of width k in order, so n − k + 1 values.

Follow-up

Divide only when you record a result, never inside the running total — keeping the total exact is what makes the subtraction safe.

Show the hint

Hold the sum as one number across the whole pass and push sum / k after each slide instead of re-adding the block.

Longest subarray with sum at most target

Medium

Given an array of non-negative integers and a target, return the length of the longest contiguous subarray whose sum is at most the target.

Follow-up

The width is not given, so the two edges move independently: right advances every iteration, left advances only while the sum is illegal.

Show the hint

Add nums[right] first, then shrink from the left with a while loop until the sum is legal again, and only then record right − left + 1.

Longest substring without repeating characters

Medium

Given a string, return the length of the longest substring that contains no repeated character.

Follow-up

The summary is now a set of characters rather than a number: one insert on the right, then as many deletes on the left as it takes. Each character is still inserted once and deleted once, so the pass stays linear.

Show the hint

If the entering character is already inside the window, keep removing characters from the left until it is not, then measure.

Windows of width k with all distinct values

Medium

Given an array and a width k, return how many windows of width k contain no repeated value.

Follow-up

A frequency map has to survive the slide — the count of distinct values must be repaired by the entering and leaving elements only, never rebuilt.

Show the hint

Increase a distinct counter when a value goes from frequency 0 to 1 and decrease it when it goes from 1 to 0; the window is valid when distinct equals k.

Maximum in every window of width k

Hard

Given an array and a width k, return the maximum of every window of width k, as n − k + 1 numbers, in O(n) total time.

Follow-up

A maximum cannot be repaired by subtraction: the element leaving may be the maximum itself, and nothing in the running value tells you the next best. The window needs a structure that remembers candidates in order.

Show the hint

Ask which elements can never be the answer again: any value with a larger value to its right is dead the moment that larger one enters. If you only ever keep the survivors, in index order, you need to add and discard at both ends — and each element is added once and discarded once, which is what keeps the whole pass linear.