Sliding Window

Both conditions fall out of one fact: the window that ends at index r is [r-k+1, r]. Everything else is reading that interval carefully.

1. 1

   The window at r. It spans [r-k+1, r], which is k elements ending at r.

2. 2

   Repair instead of recompute. Add a[r] on entry. If the window has just overflowed past size k, subtract the element that fell off the left.

3. 3

   Which element fell off. When r arrives, the element leaving is the one at r - k — it was the left end of the previous window and is now outside. So the eviction fires when r >= k.

4. 4

   When the first record is legal. The first complete window ends at index k - 1. Recording earlier reports a partial window; recording from r >= k silently drops the first one.

Two different indices, and they are not interchangeable: evict when r >= k — the leaver is a[r - k]; record when r >= k - 1 — the first full window ends at index k-1.

The window does not have to measure a total. LC 1052 runs a fixed window over a delta — the gain the window would produce — on top of a constant baseline. Recognising that the window can measure an improvement rather than a quantity is what makes that problem easy.

Overflow is real here. Sums over 10^5 elements of 10^4 and up need long, and the failure is silent.

Circular fixed windows index with % n and loop to n + k. Do not physically double the array — see sub-variant H and LC 2134.

a = [2, 1, 5, 1, 3], k = 3. Watch the two conditions firing at different moments — the first record happens one step before the first eviction.

Answer 9, the window [5, 1, 3]. Row 3 is the one to notice: the record fires while the eviction does not, because at r = 2 the window has only just become complete and nothing has fallen out yet. Shift either condition by one and you lose either the first window or the alignment of every window after it.

• Say both boundary conditions before you write the loop. The gate for this sub-variant is stating r >= k and r >= k-1 without deriving them. They are the whole difficulty of an otherwise trivial pattern.
• "Repair, don't recompute" is the transferable sentence. It is why the pattern is linear, and it is the same idea that makes every other sub-variant here work — each element enters and leaves at most once.
• A fixed window can measure a delta. LC 1052's window measures the gain from suppressing the grumpy minutes, added to a constant baseline. Windows do not have to sum the thing the problem is about.
• This skeleton is the base for E and H. Frequency matching is this loop plus a matched counter; complement windows are this loop with the size flipped to n - k. Getting A automatic pays off twice more.
• Overflow deserves a sentence, unprompted. long for products and for sums over large arrays. Saying it before you are asked is cheap and reads as experience.

• ✗Evicting a[r - k + 1] instead of a[r - k]

  Symptom: off-by-one on every window, so every answer is wrong in the same quiet way.

  Prevention: The window is [r-k+1, r]. The element that just left is the one before that: a[r-k].

• ✗Recording at r >= k instead of r >= k - 1

  Symptom: the first complete window is silently dropped — and it is often the answer.

  Prevention: The first full window ends at index k-1, so that is when recording becomes legal.

• ✗Recomputing the aggregate for each window

  Symptom: correct answers, O(nk) time, and a time-limit failure on the real constraints.

  Prevention: Add the entrant, subtract the leaver. Never look inside the window.

• ✗Accumulating in int

  Symptom: silent wrong answers on large inputs; the samples all pass.

  Prevention: long for any sum over 10^5 elements of 10^4+, and for every product window.

The loop makes one greedy decision per right endpoint. Shrink-monotonicity is what makes that decision safe.

1. 1

   The invariant. At the bottom of each iteration [l, r] is valid, and l is the smallest left boundary for which that holds. So r - l + 1 is the best window ending at r.

2. 2

   Why you may stop shrinking as soon as it is valid. Shrink-monotonicity: any further shrink is also valid but strictly shorter. There is nothing to gain by continuing, so the first valid position is the best one.

3. 3

   Why while and not if. A single insertion can violate the constraint by more than one eviction's worth — adding one character may require evicting a whole run before validity returns.

4. 4

   Why the record comes after. Inside or before the loop, the window may still be invalid, so you would record a window that is too large and does not satisfy the constraint.

The two halves of the loop shape: shrink while invalid, record after. Sub-variant C inverts both — it shrinks while satisfied and records inside. Being able to write both back to back, and say the difference out loud, is the gate.

Map hygiene is not optional. When a count reaches zero the key must be removed, or map.size() overcounts distinct values and the window never shrinks: if (map.merge(c, -1, Integer::sum) == 0) map.remove(c);. With an int[26] the equivalent is an explicit distinct counter decremented at zero.

Validity as a budget is the reframing worth stealing. LC 1004 is not count the ones — it is how much violation can I afford? (zeros <= k). That reframing turns a family of differently-worded problems into one template.

LC 1493 forces a deletion, so the answer is r - l, not r - l + 1. Same window, different read-off — and an easy off-by-one to leave in.

Longest substring without repeating characters. Step 3 needs two evictions in a row, which is exactly the case an if cannot handle.

Answer 2. Row 3 is the whole argument for while: one insertion invalidated the window by enough that a single eviction did not fix it. An if would have left bb in place and the window would have reported a length containing a duplicate.

• The precondition is the first thing to say, not the last. Is validity shrink-monotone? If you cannot answer that, you cannot justify stopping the shrink loop — and sub-variant K exists to show what happens when the answer is no.
• B and C are mirror images and must be learned as a pair. The gate explicitly asks for both, written back to back in one sitting. They differ in the shrink condition and the record position, and getting one right does not protect the other.
• Budgets generalise better than counts. At most k violations covers LC 1004, 1493, 424 and 340 with one skeleton. Candidates who reframe to a budget stop seeing four problems.
• Zero-count keys are a real correctness bug, not tidiness. A stale zero entry makes size() lie, the shrink condition never fires, and the answer is too large. It is invisible on inputs without repeats.
• Some B problems have a slicker non-shrinking form. Any max-length window can be written as sub-variant D, which never shrinks at all. Knowing both, and why D is legal, is the D gate.

• ✗Using if instead of while on the shrink loop

  Symptom: the window stays invalid, and maxima come out too large.

  Prevention: One addition can require many evictions. while for B and C; if only in the deliberate non-shrinking template D.

• ✗Recording before the shrink loop

  Symptom: records an invalid, too-large window.

  Prevention: In B the record goes after the while. In C it goes inside. Fix the pair in your head once and it stops being a coin flip.

• ✗Leaving zero-count keys in the frequency map

  Symptom: map.size() overcounts distinct keys, so the window never shrinks.

  Prevention: if (map.merge(c, -1, Integer::sum) == 0) map.remove(c); — or an explicit distinct counter for array-backed frequencies.

• ✗Returning r - l + 1 on LC 1493

  Symptom: answer exactly one too large.

  Prevention: That problem forces a deletion, so the answer is r - l. Read the required output before reusing the template's last line.

One placement decision separates a correct C from a subtly wrong one, and it follows directly from when the window is actually valid.

1. 1

   The precondition. Grow-monotone validity: satisfying at [l, r] implies satisfying at every super-window. So still satisfied is a legitimate loop condition — it can only turn off once, at the boundary.

2. 2

   The invariant. We shrink while the window still satisfies the requirement, so the last size recorded before it stops is the smallest window ending at r.

3. 3

   Why record before the remove. At the top of the loop body the window is valid. After remove(a[l]) it may not be. Recording after the removal records a window that does not satisfy the requirement — always too small, always wrong.

4. 4

   The sentinel. If the requirement is never satisfied, best is untouched. Return 0 (or the empty string) rather than leaking Integer.MAX_VALUE to the caller.

Record placement is the entire difference from B: in C, record inside the while, before remove. Recording after the shrink records an invalid window.

LC 76's have/need counter makes validity O(1). required is the number of characters still owed, multiplicity included; only a needed character reduces the debt, and only removing a needed character re-owes it.

need[c] is allowed to go negative, and that is the point. Surplus characters push the entry below zero, which is exactly what makes the > 0 and == 0 tests correct without a second map. Being able to explain that is the C gate.

LC 1234 inverts the mental model: validity depends on what is outside the window, not inside it. Same loop shape, and a genuinely different way of reading the predicate.

a = [2, 3, 1, 2, 4, 3], target = 7. Steps 4 and 5 each shrink more than once, recording before every removal.

Answer 2, the window [4, 3]. Notice what would happen with the record moved after the remove: on the final step you would record the window [5,5] of size 1, whose sum is 3 — and confidently return an answer that does not satisfy the requirement at all.

• Grow-monotonicity is the licence, and negatives revoke it. LC 209 works because the values are positive. LC 862 is the same question with negatives allowed, and the window collapses — that is why 862 lives in sub-variant I, not here.
• The record position is the single most-tested detail. Interviewers who know the pattern watch for it specifically, because it separates people who derived the loop from people who half-remember it.
• need[] going negative is a feature worth narrating. It encodes surplus, which is what lets one array answer both 'do I still owe this character?' and 'can I afford to drop it?' without a second structure.
• Validity can live outside the window. LC 1234 asks whether what remains outside is balanced. The loop is untouched; only the predicate moves. Recognising that is worth more than the problem.
• Always handle the never-satisfied case explicitly. A sentinel Integer.MAX_VALUE escaping into the return value is a common and embarrassing failure on the empty-answer test.

• ✗Recording after the shrink

  Symptom: records an invalid, too-small window — and the returned length cannot actually be achieved.

  Prevention: In C, record inside the while, before remove.

• ✗Using B's loop condition

  Symptom: shrinking while invalid never fires here, so the window never contracts and you return the first satisfying length rather than the smallest.

  Prevention: C shrinks while satisfied. Write B and C side by side until the pairing is automatic.

• ✗Applying C to a sum problem with negatives

  Symptom: wrong answers on mixed-sign input; every positive-only test passes.

  Prevention: Ask first: does adding an element monotonically move the aggregate? If not, prefix sums plus a deque — LC 862.

• ✗Returning the sentinel

  Symptom: Integer.MAX_VALUE or a garbage substring on inputs with no valid window.

  Prevention: return best == Integer.MAX_VALUE ? 0 : best; — and the empty string for LC 76.

The claim looks too good: the window can be invalid for long stretches, yet its final size is exactly right. Four steps show why.

1. 1

   Only the maximum length matters. We are not asked for the window, its contents, or where it sits — only how wide the best legal one was.

2. 2

   An invalid window slides, preserving its size. Adding one element and removing one element leaves the width unchanged. So the window never loses ground it has already won.

3. 3

   It grows only into genuinely better territory. The width increases exactly when a step keeps the window valid — which means a legal window of the new, larger size actually exists at that moment.

4. 4

   Therefore the final width is the answer. The window is a high-water mark. It never contracts, and it only expands on legal ground, so n - l at the end equals the maximum legal width.

Why a stale maxF is safe in LC 424 — reconstruct this, interviewers ask: if maxF is stale it is an overestimate of the current window's best frequency, which makes size - maxF an underestimate of the replacement cost, which makes the window look more valid than it is. So the window can only fail to shrink — never shrink wrongly. And it cannot report a size larger than a genuinely achievable one, because the recorded size was achievable back when maxF was accurate.

maxF is deliberately never decreased on a slide. Recomputing it would cost O(26) per step and buy nothing, precisely because of the argument above. Leaving it stale is a decision, not an oversight — say so.

There is no best variable. Candidates often add one out of habit and then wonder why it always equals n - l. It does, by construction.

Longest repeating character replacement, one replacement allowed. From step 5 onward maxF is stale — and the answer is still exactly right.

Answer 4 — the window AABA found at step 4. From step 5 the window is never valid again, so it simply slides three times without changing width. maxF stayed at 3 the whole way, overstating the true best frequency, and the overstatement only ever made the window slower to slide, never wrong.

• The stale-maxF argument is the gate, not the code. The gate says explicitly: explain why a stale maxFreq cannot produce a wrong answer. If you can only reproduce the code, you memorised it.
• The error is one-directional, which is why it is safe. Overestimating maxF underestimates cost, which makes the window look more valid. It can only delay a slide. A stale value that could make the window look less valid would be a bug.
• D generalises past its two famous problems. Any max-length window can be written non-shrinking. Most people learn it as a quirk of LC 424 and never transfer it.
• No recording means no off-by-one. The whole class of record-position bugs that plague B and C simply does not exist here, which is a real argument for the form.
• The window's contents are meaningless at the end. Only the width is guaranteed. If the problem wants the actual substring, use B.

• ✗Using while instead of if

  Symptom: still correct, but you have quietly rebuilt sub-variant B and lost the simplification.

  Prevention: if is the point. while is right for B and C; D is the deliberate exception.

• ✗Recording a best inside the loop

  Symptom: harmless but redundant — and it signals you have not understood why n - l works.

  Prevention: There is no record. The answer is the final width.

• ✗Recomputing maxF on every slide

  Symptom: O(26n) instead of O(n), and it suggests the staleness argument was never made.

  Prevention: Leave it stale, on purpose, and be ready to justify it.

• ✗Using D for a minimum-length or counting question

  Symptom: nonsense output — the window is only meaningful as a high-water mark.

  Prevention: D answers maximum width and nothing else.

The counter is only correct if it tracks exact equality. Tracking at least silently accepts windows with too many of a character.

1. 1

   The definition. matched = the number of distinct keys whose window count is exactly the required count. Not at least — exactly.

2. 2

   The validity test. The window is valid iff matched == distinctNeeded. One integer comparison, O(1), no scanning.

3. 3

   Why exact and not at-least. If overshooting left a key counted as matched, a window with three as where two are needed would read as valid. So passing need[c] must decrement matched again.

4. 4

   Four branches, not two. Symmetry: on add, a key can cross into exact (== need) or out of exact (== need + 1). On remove, it can cross out of exact (was == need) or back into it (was == need + 1). All four must be handled.

Where this template is normally written incorrectly: the two symmetric need + 1 branches. Both transitions — into exact and out of exact — must be handled on both add and remove.

LC 438 is LC 567 that keeps going. Same machine; one returns on the first match, the other collects every start position. If 567 is solid, 438 is free.

LC 30 moves to word granularity. The window slides by whole words, so you run wordLen separate window phases — one per offset. The counter logic is unchanged; only the unit is.

matched may legitimately go negative while the window is full of irrelevant characters. That is fine — it is a signed score, not a count of successes, and it repairs itself as those characters are evicted.

need = {a:1, b:1}, distinct = 2, window size 2. Watch matched dip negative on irrelevant characters and recover as they are evicted.

Found at index 3, the substring ba. The negative excursion is not a bug: irrelevant characters overshoot their need of zero, and every one of them is undone by the matching evict branch. Drop either need + 1 branch and the counter never returns to a truthful value.

• Count the branches out loud while writing. The gate asks for all four transitions. Candidates who narrate into-exact and out-of-exact, on add and on remove essentially never miss one.
• Exactness is what makes the counter sound. An at-least counter is a different tool for a different job — see LC 76 in sub-variant C. Mixing the two produces code that passes anagram tests and fails on surplus characters.
• This is sub-variant A plus a counter. The fixed-window skeleton is unchanged; only the aggregate got cleverer. Saying that shows the family rather than the instance.
• O(1) validity is the whole point. If you find yourself comparing arrays inside the loop, you have written the naive version with extra steps.
• Word-granular windows are the same idea rescaled. LC 30's wordLen phases surprise people, but nothing about the counter changes — only what counts as one element.

• ✗Handling only the == need branches

  Symptom: windows with a surplus of one character are accepted as valid.

  Prevention: Both need + 1 branches are required, on add and on remove. Four branches total.

• ✗Tracking at least instead of exactly

  Symptom: same failure, arrived at differently — overshoot never un-matches.

  Prevention: matched counts keys at exact equality. At-least logic belongs in C's have/need form.

• ✗Forgetting to evict before the next iteration

  Symptom: the window grows past its fixed size and every later verdict is meaningless.

  Prevention: In the fixed-size form, evict s[r - len + 1] at the bottom of each iteration.

• ✗Leaving stale zero entries when using a map

  Symptom: distinct-key counts drift and the validity test silently stops firing.

  Prevention: Remove keys at zero, or maintain an explicit distinct counter alongside the array.

Both formulas are direct consequences of monotonicity — the same reasoning, applied in opposite directions.

1. 1

   F1 — the setup. Validity is shrink-monotone, and we shrink until [l, r] is valid. Every sub-window of a valid window is valid.

2. 2

   F1 — the block. So every subarray ending at r and starting anywhere in [l, r] is valid. That is r - l + 1 subarrays, certified by one comparison.

3. 3

   F2 — the setup. Validity is grow-monotone, and we shrink while still valid. The loop therefore stops with l one position past the last start that worked.

4. 4

   F2 — the block. Every start in [0, l-1] gives a super-window of a valid window, so all of them are valid too. That is l subarrays.

Pick the formula from the monotonicity, not from the wording: count += r - l + 1 when validity is shrink-monotone (at-most style); count += l when it is grow-monotone (contains-all style).

LC 713 needs k <= 1 guarded. No product of positive integers is below 1, so without the early return the shrink loop divides past l = r and misbehaves.

Products overflow. Accumulate in long, and remember that the division-based shrink is only valid because every element is positive.

F is a prerequisite for G, not a sibling. The at-most-K subtraction identity is defined over counts of subarrays — which is precisely what F1 produces. Learning G first is why people misapply the identity to lengths.

a = [10, 5, 2, 6], k = 100. One comparison per step, and each one banks several subarrays at once.

Answer 8. Step 4 banked three subarrays — [6], [2,6], [5,2,6] — from a single comparison. Writing count++ there instead would return 4, which looks like a small bug and is actually a missing batch.

• Name the monotonicity before you pick the formula. The gate asks exactly this: when count += r - l + 1 versus count += l, and how each ties to shrink- or grow-monotonicity. Memorising the two lines without the tie is how they get swapped.
• The +1 has a reason, and it is worth saying. F1 counts a block that includes l; F2's shrink already stepped past the last valid start. Two different geometries, not two arbitrary formulas.
• This is two pointers §1.K in window clothing. One comparison certifying a block of candidates. If that transferred for free, the pattern structure is doing its job.
• Counting and measuring are different questions. A counting window and a longest-window can look identical and need different bookkeeping. Read the required output first.
• Guards and overflow deserve a sentence each. k <= 1 and long are both silent failures on LC 713, and both are cheap to mention before being asked.

• ✗Writing count++ instead of the batch

  Symptom: severe undercount that reads like an off-by-one.

  Prevention: One settled window certifies a whole block of start positions. Count the block.

• ✗Using r - l + 1 where validity is grow-monotone

  Symptom: wrong counts on contains-all problems, in the right ballpark.

  Prevention: Grow-monotone means the shrink stopped past the last valid start: the answer is count += l.

• ✗Forgetting the k <= 1 early return in LC 713

  Symptom: the shrink loop runs past l = r and divides by the wrong element.

  Prevention: if (k <= 1) return 0; — no positive product is below 1.

• ✗Accumulating the product in int

  Symptom: silent overflow, plausible-looking wrong answer.

  Prevention: long for the running product, always.

The subtraction is obvious once stated and easy to misapply, so the precondition matters as much as the identity.

1. 1

   What atMost(K) counts. Every subarray whose distinct-count (or sum, or odd-count) is <= K. A plain F1 counting window computes it.

2. 2

   What atMost(K-1) counts. Every subarray at <= K-1. Because the constraint is strictly tighter, this set is a subset of the first.

3. 3

   The difference. Subarrays counted by the first and not the second are exactly those with a value of precisely K. That is the answer.

4. 4

   Why it must be counts. The set-difference argument works because both terms count the same kind of object. Lengths are not additive over sets, so subtracting two maxima is meaningless.

The identity, and the precondition that makes it legal: exactly(K) = atMost(K) - atMost(K-1), valid only when atMost counts subarrays (formula F1) and is monotone non-decreasing in K. It does not work for 'longest with exactly K'.

LC 930 and 1248 are the same shell. Replace f.size() > k with sum > k or oddCount > k and nothing else changes. LC 1248 is the transfer test: if you do not see that k odd numbers is a relabelling of sum of a 0/1 array, the pattern has not landed.

LC 992 is the one that cannot be faked. Exactly K distinct is genuinely unreachable with one window, which is why the gate asks you to explain why, not just to produce the code.

Verified reference values: [1,2,1,2,3] with k = 2 gives 7; [1,2,1,3,4] with k = 3 gives 3. Useful for checking an implementation before submitting.

Two runs of the same machine, side by side. Each column shows the window after shrinking and the batch it contributes.

atMost(2) = 12, atMost(1) = 5, so exactly(2) = 7 — matching the verified value above. Look at row 5: the at-most-2 window had to evict three elements to admit the 3, while the at-most-1 window evicted everything. Neither run ever needed to know what exactly two means.

• Be ready to explain why one window cannot do it. The gate asks for this directly. The answer: a window below K is not invalid, so the shrink loop has no condition to fire on — there is nothing to shrink against.
• State the precondition unprompted. atMost is monotone in K and counts subarrays. Both halves matter, and the second is what stops people applying the identity to length problems.
• The relabelling is the transfer test. LC 1248's k odd numbers is LC 930's sum equals S over a 0/1 array. Seeing that without being told is the point of including both.
• Monotone relaxation is a general technique. When a predicate is not monotone, look for a monotone one whose counts differ by what you want. That idea outlives this pattern.
• Two passes is still linear. Candidates sometimes resist the double run as wasteful. 2 * O(n) is O(n), and the alternative is a window that does not exist.

• ✗Applying the identity to a length answer

  Symptom: nonsense output — subtracting two maxima means nothing.

  Prevention: The identity is valid only for counts of subarrays. For longest with exactly K you need a different approach entirely.

• ✗Writing atMost with a length-style record

  Symptom: the subtraction silently operates on the wrong quantity.

  Prevention: atMost must use formula F1: count += r - l + 1 after shrinking.

• ✗Assuming atMost is monotone without checking

  Symptom: the difference can go negative or overcount.

  Prevention: Confirm that raising K can only admit more subarrays. If it cannot, the identity does not apply.

• ✗Trying to shrink toward exactly-K with one window

  Symptom: an infinite loop, or a shrink condition that never fires.

  Prevention: There is no such condition. That is the entire reason this sub-variant exists.

The reframing is a one-line argument, and once made, the implementation is a sub-variant you already own.

1. 1

   What you take is two pieces. A prefix of length i and a suffix of length k - i. Sliding those jointly is awkward — there is no single boundary to move.

2. 2

   What you leave is one piece. Everything not taken is the contiguous block between them, of size exactly n - k. One block, two boundaries that move together.

3. 3

   The objective inverts cleanly. The total of the array is fixed. Maximising what you take is therefore exactly minimising what you leave.

4. 4

   So the answer is a subtraction. answer = total - minWindow, where minWindow is a plain fixed window of size n - k.

The recognition that is the whole problem: 'take k from either end' is 'minimise a fixed window of size n - k in the middle'. Seeing that inside thirty seconds is the gate.

Guard keep == 0. When k == n you take everything and there is no window at all; without the early return the loop records nothing and the answer comes back as a sentinel.

LC 1658 flips a sum instead of a size. Shortest prefix + suffix summing to x becomes longest middle subarray summing to total - x — and a longest-subarray-with-target-sum window is sub-variant B.

Circular windows are a cousin, not the same thing. Index with % n and loop from k to n + k. Never physically double the array — and if you do double it, remember to double the bounds too, which is the classic half-fix that misses every wrap-around window.

a = [1, 2, 3, 4, 5, 6, 1], k = 3, so total = 22 and the block you leave has size n - k = 4. Just slide it.

answer = total - minWindow = 22 - 10 = 12 — take 1, 2 from the front and 1 from the back. Four window positions and one subtraction, versus enumerating every split of k between the two ends.

• The recognition is timed, and deliberately so. The gate is thirty seconds, because in an interview the flip either arrives immediately or you spend the slot fighting two pointers that will not cooperate.
• Say the invariant that licenses the flip. The total is fixed, so maximising what I take is minimising what I leave. One sentence, and the rest is a fixed window.
• The flip generalises past sizes to sums. LC 1658 inverts a target sum rather than a length. Same move, different quantity — which is the sign you have the pattern and not the problem.
• Circular indexing beats array doubling. % n is less code and cannot desynchronise the bounds. Doubling the array while forgetting to double the loop bound is a specific, common bug.
• Watch for the degenerate case in the problem statement. k == n is legal in LC 1423 and it makes the window vanish. Handle it before the loop.

• ✗Trying to slide two windows at the ends

  Symptom: tangled index arithmetic and an off-by-one you cannot locate.

  Prevention: Flip to the complement. One block, two boundaries that move together.

• ✗Forgetting the keep == 0 guard

  Symptom: the minimum is never recorded and a sentinel value escapes.

  Prevention: If k == n you take the whole array — return total before entering the loop.

• ✗Doubling the array without doubling the bounds

  Symptom: every wrap-around window is missed, and the answer is right on non-circular inputs.

  Prevention: Loop i from k to n + k and index with % n. Better still, do not double at all.

• ✗Applying the flip when the complement is not contiguous

  Symptom: the window is meaningless and the subtraction is arbitrary.

  Prevention: The flip is only valid when what you leave behind is a single block.

One observation eliminates almost everything, and what is left is trivially ordered.

1. 1

   The domination rule. If j < i and a[j] <= a[i], then j can never be the maximum of any window that contains i — i is both later and at least as large, so it survives every window j does.

2. 2

   What survives. Discarding every dominated index leaves a sequence whose values are strictly decreasing from front to back. Nothing else can be the max of anything.

3. 3

   So the front is the max. The front holds the largest surviving value, and by construction every survivor is still a live candidate.

4. 4

   Expiry is positional. The only other way an element stops mattering is by falling out of the window — a fact about its index. Hence indices in the deque, and dq.first <= r - k as the expiry test.

Order of operations, and why indices: push (popping dominated tails) -> expire the front by index -> read. Expiring by index is the reason the deque stores indices, not values.

LC 862 is why this sub-variant also owns the negatives case. With negatives, extending r can decrease the sum, so sum >= K is not grow-monotone and there is nothing to shrink against — the plain window of LC 209 simply dies.

The fix is a deque over prefix sums. Work on P, wanting the smallest i - j with P[i] - P[j] >= K. The deque holds indices with P strictly increasing. Pop from the front while the pair already qualifies — that j can never be beaten by a later i, since any later i gives a longer subarray. Pop from the back while P[last] >= P[i] — index i is both later and has a smaller prefix, so last is dominated on both axes and is dead weight.

Loop i <= n, not i < n. The prefix array has n + 1 entries, and stopping early misses the full-array answer.

LC 1438 runs two deques, one for the max and one for the min, inside a variable window. Both must expire against the same l, or they desynchronise and the window's spread is computed from two different windows.

Verified reference values for 862: [2,-1,2], K=3 gives 3; [1,2], K=4 gives -1; [84,-37,32,40,95], K=167 gives 3.

a = [1, 3, -1, -3, 5], k = 3. Watch step 5 evict the entire deque in one go — that is domination clearing out three dead candidates at once.

Output [3, 3, 5]. Step 5 is the domination argument paying off: indices 1, 2 and 3 were all older and smaller than the incoming 5, so all three became permanently irrelevant in a single sweep. Across the whole run each index is pushed once and popped once — which is why the total cost is O(n) even though one step popped three.

• Amortise the cost out loud. Each index enters the deque once and leaves once, so the inner while does not make this quadratic. Interviewers do ask, and O(n) amortised with that one-line reason is the answer.
• Indices, always — and say why. You cannot expire by value, because you would not know which copy fell out of the window. That is the reason, and it is short.
• The order of operations is part of the template. Push, expire, read. Reading before expiring returns a max that has already left the window.
• 862 is the capstone of the whole pattern. It is where the monotonicity test, prefix sums and the deque all have to be held at once — which is exactly why the gate names it and says to re-read the deque invariant on failure.
• Two deques must share one left boundary. In LC 1438 the max-deque and min-deque both expire against the same l. Expiring only one is a desynchronisation bug that produces plausible, wrong spreads.

• ✗Storing values instead of indices

  Symptom: you cannot tell when an element leaves the window, so expiry becomes impossible.

  Prevention: Always store indices; read the value as a[dq.peekFirst()].

• ✗Using < instead of <= when popping the tail

  Symptom: duplicates linger in the deque — usually still correct for a plain max, and broken the moment you count maxima.

  Prevention: Use <= for a strictly decreasing deque, and make it a deliberate choice rather than a coin flip.

• ✗Expiring only one deque in the two-deque form

  Symptom: the max and min deques drift apart and describe different windows.

  Prevention: Both deques expire against the same l, every iteration.

• ✗Looping i < n in LC 862

  Symptom: the full-array answer is missed.

  Prevention: The prefix array has n + 1 entries — loop i <= n.

It is worth being precise about why the cheaper structure fails here, because the same question decides the tool on every window problem with an unusual aggregate.

1. 1

   What the deque relied on. Domination: an element that is both older and smaller than another can never again be the answer. That is what let the deque throw most of the window away.

2. 2

   Medians admit no domination. The median depends on the whole distribution. A small element is not irrelevant — it is part of what determines where the middle sits. Nothing can be discarded.

3. 3

   So keep the window fully ordered. Two heaps split it at the median: the max-heap holds the lower half, the min-heap the upper. Rebalance after every insertion and removal so the sizes differ by at most one.

4. 4

   Lazy deletion handles the eviction. A binary heap cannot remove an arbitrary interior element. So mark the outgoing element as dead and physically discard it only when it surfaces at the top.

The dividing line between I and J: reach for a deque when an older element can be dominated into irrelevance; reach for an ordered multiset when it cannot. Max and min dominate; medians and k-th values do not.

The cost is O(n log k), and that is the signal. If the constraints do not allow a log factor, the intended solution is probably not a window at all — re-run the monotonicity test from §2.1 before committing.

Median arithmetic overflows. For an even-sized window the median is the mean of two middles; compute it as lo + (hi - lo) / 2.0 rather than (lo + hi) / 2 to avoid overflowing on large values.

A TreeMap multiset is often the shorter answer under time pressure. It sidesteps lazy deletion entirely at the cost of a constant factor — worth knowing as the pragmatic fallback.

a = [1, 3, -1, -3, 5], k = 3. The heaps are shown as lower half | upper half; for an odd window the lower half carries the extra element, so the median is its top.

Medians [1, -1, -1]. Notice step 3: the outgoing element was 3, which sat in the min-heap, and the incoming 5 replaced it there — but in a real implementation 3 is not removed immediately. It is marked dead and discarded when it next reaches a heap top, which is what lazy deletion buys you.

• Name the missing domination relation. Max has one, median does not is the whole reason this sub-variant exists. It is a better answer than medians are harder.
• Rebalancing is an invariant, not a cleanup step. The size difference must be restored after every insertion and removal, or the median is read from the wrong side.
• Lazy deletion is a heap workaround, not a window idea. It exists because binary heaps lack arbitrary removal. Saying that distinguishes the data structure's limitation from the algorithm's.
• Know the pragmatic alternative. A TreeMap multiset trades a constant factor for much less code. Under interview time pressure that is often the better call, and saying so reads as judgement.
• Both problems here are optional by design. The table marks them ○. Skipping them is a legitimate choice unless you are targeting a bar that asks for them.

• ✗Reaching for a deque because the window is a maximum-like query

  Symptom: the deque discards elements the median still depends on, and the answers are quietly wrong.

  Prevention: Ask whether a domination relation exists. If it does not, the deque is invalid.

• ✗Forgetting to rebalance after removal

  Symptom: the heaps drift out of size balance and the median is read from the wrong heap.

  Prevention: Rebalance after every insertion and every removal, as part of the same operation.

• ✗Eagerly removing an arbitrary element from a heap

  Symptom: O(k) per removal, which turns the whole solution quadratic.

  Prevention: Use lazy deletion: mark it dead, discard it when it reaches the top.

• ✗Computing an even-window median as (lo + hi) / 2

  Symptom: integer overflow on large values, and integer truncation on odd sums.

  Prevention: lo + (hi - lo) / 2.0.

Both problems look like textbook windows. Understanding precisely which monotonicity each one breaks is what makes the correct tool obvious.

1. 1

   The contract a window requires. Either shrink-monotone (valid implies every sub-window valid) or grow-monotone (satisfying implies every super-window satisfying). One of the two must hold.

2. 2

   LC 560 breaks both. With negatives allowed, growing r can decrease the sum. So sum == k is neither shrink- nor grow-monotone, and there is no shrink rule that could exist. The correct tool is a prefix sum plus a hash map, seeded with (0 -> 1) so that a prefix which itself equals k is counted.

3. 3

   LC 395 breaks shrink-monotonicity specifically. At least k repeats can be repaired by adding a character — a window that is invalid now may become valid as it grows. So shrinking on invalidity is exactly the wrong move.

4. 4

   The 395 fix is to restore monotonicity by force. Freeze a parameter. For each fixed target number of distinct characters d from 1 to 26, at most d distinct is monotone, so an ordinary window works; inside it, additionally require every present character to have count >= k. Twenty-six legal windows replace one illegal one.

The test to run before writing a single line: does adding an element monotonically move the aggregate? If no, it is not a window — and the gate for this pattern is saying so before you write code, not after it fails.

The (0 -> 1) seed in LC 560 is not decoration. Without it, a prefix that itself equals k — a subarray starting at index 0 — is never counted, and the answer is short by exactly those cases.

Freezing a parameter is a general escape hatch. When a predicate is non-monotone in one variable, fixing that variable often restores monotonicity in the rest. The cost is a factor of however many values you must try — 26 here, which is a constant.

LC 395 also has a divide-and-conquer solution: split on any character occurring fewer than k times, since no valid substring can cross it. Worth knowing as the alternative.

LC 862 is the third member of this family but lives in sub-variant I, because its fix is a monotonic deque rather than a hash map or a frozen parameter.

a = [1, -1, 1, 2], k = 2. Look at step 2 first: the running sum falls as the window grows, which is the monotonicity failure in one line.

Answer 2 — the subarrays [-1, 1, 2] and [2]. Step 4 found both at once: two earlier prefixes equalled 1, so two different start points produce a sum of 2 ending here. A window could never have found the first of those, because reaching it requires shrinking past a point where the sum went down.

• The gate here is about restraint, not technique. Given a new subarray problem with negatives, correctly say 'not a window' before writing code. Failing that gate means you are pattern-matching on shape instead of monotonicity.
• Name which monotonicity broke, not just that something did. 560 breaks both directions; 395 breaks shrink-monotonicity only. The distinction points straight at the fix.
• The seed value is a real correctness detail. (0 -> 1) in the prefix map is the difference between counting subarrays that start at index 0 and silently dropping them.
• Freezing a parameter is the transferable move. It reappears well beyond windows: when something is not monotone in one dimension, fix that dimension and pay a constant factor.
• These two problems are the highest-value items in the pattern. They are the only ones that teach when not to reach for the window — which is the difference between someone who has done the problems and someone who can solve an unseen one.

• ✗Applying a window to a sum problem with negatives

  Symptom: wrong answers on mixed-sign input; every positive-only test passes.

  Prevention: Before writing: does adding an element monotonically move the aggregate? If no, prefix map or deque.

• ✗Omitting the (0 -> 1) seed in the prefix map

  Symptom: every subarray starting at index 0 is missed.

  Prevention: Seed seen.put(0L, 1) before the loop.

• ✗Shrinking on invalidity in LC 395

  Symptom: the window discards a prefix that a later character would have repaired.

  Prevention: At least k is not shrink-monotone. Freeze the distinct count and run one monotone window per value of d.

• ✗Concluding no window and stopping there

  Symptom: a correct diagnosis with no answer attached.

  Prevention: Each failure has a named fix: hash map for 560, frozen parameter for 395, deque on prefix sums for 862.