Variable Window

What is this?

Three problems that look like the same grow-and-shrink loop and are not. The first genuinely is one, wrapped in a streaming interface. The second breaks the technique's central assumption and needs the free variable removed before a window applies at all. The third contains negative numbers, which makes a window not merely awkward but wrong.

This chapter is where you learn to check the assumption instead of reaching for the template.

💡 Fun fact: Shortest Subarray with Sum at Least K is the same sentence as an easy sliding-window problem with one word changed — the values may be negative. That single change is fatal: a growing window's sum is no longer non-decreasing, so "shrink while the sum is too large" can discard the answer. The correct solution keeps a deque of prefix-sum indices in increasing order, popping from the front when a candidate qualifies and from the back when a new prefix is smaller than an older one — because an older, larger prefix can never beat a newer, smaller one for any future endpoint.

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

The one-line idea: the template requires the constraint to move one way as the window grows. When it does not, either remove the free variable so it does, or drop the window for a structure that can discard dominated candidates.

1. Why "at least k" breaks it

For Longest Substring with At Least K Repeating Characters, consider "aaabb" with k = 3. The window "aab" fails — b appears once. Extending it to "aabb" still fails. Extending to "aaabb" succeeds. An invalid window became valid by growing, which is precisely what the shrink rule assumes cannot happen.

Two repairs, both worth knowing:

Fix the target. Run the ordinary at-most-t-distinct window for each t from 1 to 26, and inside each run additionally require that every character present appears at least k times. With t fixed the constraint is monotonic again, so the template is valid. Total cost O(26n).

Divide and conquer. Any character appearing fewer than k times in the whole string can never be part of an answer, so split the string on it and recurse into the pieces. When no such character exists, the whole string qualifies.

2. Why negatives break it, and the deque

from collections import deque
prefix = [0]
for x in nums: prefix.append(prefix[-1] + x)

dq, best = deque(), len(nums) + 1
for i, p in enumerate(prefix):
    while dq and p - prefix[dq[0]] >= k:      # this endpoint qualifies
        best = min(best, i - dq.popleft())
    while dq and prefix[dq[-1]] >= p:         # an older, larger prefix is dominated
        dq.pop()
    dq.append(i)
return best if best <= len(nums) else -1

Both pops are essential and they do different jobs. The front pop harvests answers — once a window qualifies, no longer window starting there can be better, so it is removed permanently. The back pop discards prefixes that are larger than a newer one: a bigger prefix arriving earlier can never produce a shorter qualifying window than a smaller prefix arriving later.

3. The streaming variant

At Most K Distinct Characters in a Stream is the honest window of the three, with the twist that characters arrive one at a time and you must answer after each. The state is the usual count map plus a live-key count, and the discipline is the same: delete a key the moment its count reaches zero, or the distinct count silently drifts.

4. A 30-second worked example (the deque)

nums = [2, -1, 2], k = 3. The answer is 3 — the whole array.

prefix:  [0, 2, 1, 3]
          i=0  i=1  i=2  i=3

i=0 p=0   dq empty         → push 0            dq=[0]
i=1 p=2   2-0=2 < 3        → no harvest
          prefix[0]=0 < 2  → no domination pop → push 1   dq=[0,1]
i=2 p=1   1-0=1 < 3        → no harvest
          prefix[1]=2 >= 1 → pop 1 (dominated) → push 2   dq=[0,2]
i=3 p=3   3-prefix[0]=3 >= 3 → harvest: 3-0 = 3 ✓  popleft
          3-prefix[2]=2 < 3  → stop
                                          answer = 3

Note the domination pop at i=2: prefix 2 was larger than the newer prefix 1, so it could never yield a shorter window and was discarded. A plain sliding window, having shrunk past the -1, would never have found this.

5. Where you'll actually meet this

• Monitoring and alerting. Shortest burst whose total crosses a threshold, over metrics that are deviations and therefore signed.
• Financial analysis. Shortest period of cumulative gain over a target, where daily returns are negative as often as positive.
• Streaming text processing. Bounded-vocabulary constraints over an unbounded input, with memory fixed in advance.
• Quality control. Shortest run meeting a cumulative tolerance where individual measurements can be under or over.

6. Problems in this chapter

▶ At Most K Distinct Characters in a Stream

Report, after each arriving character, whether the recent window holds at most k distinct values. The genuine template, with a streaming interface.
Pattern: grow-and-shrink with a count map. Target: O(1) amortised per character, O(k) space.

▶ Longest Substring with At Least K Repeating Characters

Longest substring in which every present character appears at least k times. Not monotonic — fix the distinct count and run the window 26 times, or split on disqualifying characters and recurse.
Pattern: fixed-target windows, or divide and conquer. Target: O(26n), or O(n log n) average.

▶ Shortest Subarray with Sum at Least K

Shortest subarray summing to at least k, with negatives allowed. A monotonic deque over prefix sums; a sliding window is provably wrong here.
Pattern: monotonic deque over prefix sums. Target: O(n) time, O(n) space.

7. Common pitfalls 🚫

• Using a sliding window with negatives. It looks right, passes positive-only tests, and is wrong. Say why.
• Assuming "at least" is monotonic. Construct the two-window counter-example before trusting the template.
• Only popping the front of the deque. Without the domination pop the deque is not monotonic and the answer is not minimal.
• Popping the front without harvesting. Once a window qualifies, record it — that index will never be useful again.
• Off-by-one in the prefix array. prefix has n + 1 entries and the window length is a difference of indices into prefix, not into nums.
• Not deleting zero-count keys in the streaming problem, which corrupts the distinct count.
• Recursing on the whole string in the divide-and-conquer version when no character disqualifies — that is the base case, not a recursion.

8. Key takeaways

1. Test monotonicity first. It is the assumption the entire technique rests on.
2. "At most" is monotonic. "At least" is not. One word changes the algorithm.
3. Remove the free variable — fixing the distinct count restores the template's validity.
4. Negatives mean a deque over prefix sums, not a window.
5. Two pops, two purposes: front harvests answers, back discards dominated prefixes.
6. Smaller and newer beats larger and older — the domination rule, and the reason the deque stays monotonic.
7. Why interviewers like it: these problems are dressed to look routine. The signal is entirely in whether you check the assumption before writing the loop.

Order: At Most K Distinct Characters in a Stream → Longest Substring with At Least K Repeating Characters → Shortest Subarray with Sum at Least K.