</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

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: the usual fix is to fix the number of distinct characters so a window applies, and the alternative is to split the string on disqualifying characters. 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.

Choosing the variable-window technique

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 of prefix value, popping from the front when a candidate qualifies and from the back when a new prefix is no larger 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.


Core 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 because 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. For each t from 1 to 26, slide a window that holds at most t distinct characters and count how many of them have reached k occurrences. The window is valid when it holds exactly t distinct characters and all t have count at least k. With t fixed the constraint is monotonic again, so the template is valid. Total cost O(26n) time and O(26) space.

Divide and conquer. Any character appearing fewer than k times in the current segment can never be part of an answer, so split the segment on it and recurse into the pieces. When no such character exists, the whole segment qualifies. A piece never contains the character it was split on, so the recursion is at most 26 levels deep and the total cost is O(26n) time, not O(n^2). The lesson's version copies the pieces, so its space is O(26n) worst case.

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 start qualifies, a later endpoint can only give a longer window from it, so it is removed permanently. The back pop discards prefixes that are no smaller than a newer one: a bigger prefix arriving earlier can never produce a shorter qualifying window than a smaller prefix arriving later. Every index is pushed and popped once, so the time is O(n), and the prefix array plus the deque take O(n) space.

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 distinct counter, and a deque of the live characters so the left edge can evict from the front instead of indexing into a string. The discipline is the same as the offline problem: decrement distinct the moment a count reaches zero, or it silently drifts. The deque costs O(window) space, which can be the whole stream when k is large. If memory matters, keep each live character's last-seen index in an OrderedDict instead: at most k + 1 entries, so O(k) space, at the price of losing per-character counts.


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

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

Monotonic-deque trace over prefix sums

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. The prefix array is [0, 2, 1, 3], and the answer comes from index 0 at i=3, where 3 - 0 >= 3.


5. Where you'll actually meet this

  • Signed metrics. Shortest stretch whose total crosses a threshold, when the readings are changes and can be negative.
  • Cumulative gain. Shortest period of net gain over a target, where daily changes go both ways.
  • Streaming input. Bounded-vocabulary constraints over an unbounded input, with memory fixed in advance.

6. Problems in this chapter

At Most K Distinct Characters in a Stream

After each arriving character, report the length of the longest suffix window with at most k distinct characters, and remember the longest seen so far. The genuine template, with a streaming interface.
Pattern: grow-and-shrink with a count map, a distinct counter and a deque of live characters. Target: O(1) amortised per character, O(window) space; an OrderedDict of last-seen indices gets O(1) per character and 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: split on disqualifying characters and recurse, or fix the distinct count and run the window 26 times.
Pattern: divide and conquer on a rare character, or fixed-target windows. Target: O(26n) time either way (recursion at most 26 deep); O(26) space for the windows.

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 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. Be ready to 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 decrementing distinct when a count reaches zero 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.
  • Calling the divide-and-conquer version O(n^2). Each split removes a letter, so the depth is at most 26 and the cost is O(26n).

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. That is 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, then Longest Substring with At Least K Repeating Characters, then Shortest Subarray with Sum at Least K.

At Most K Distinct Characters in a Stream

Core idea: This is the streaming version of Longest Substring with At Most K Distinct Characters. There the whole string sits in memory and you sweep two pointers over it. Here the characters arrive one at a time, so you keep the invariant incrementally: a count map char -> count and a distinct counter (the number of keys with a positive count). An arrival bumps a count, and distinct goes up if the count was zero. While distinct > k, you evict the oldest buffered character, decrementing its count, and distinct goes down when a count reaches zero. Each character is added once and removed at most once, so the cost is O(1) amortized per character.


Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.