Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Sliding window

When a window is the wrong tool

Lesson · 10 min read · Sliding window · When a window is the wrong tool

Questions about contiguous runs that a window cannot answer, how to recognise them in a minute, and the prefix-sum methods that replace it.

Three ways a window question goes wrong

A window needs a validity test that survives shrinking (for longest and counting) or growing (for shortest), and a state that updates in O(1). Questions fail that in three recognisable ways.

The questionWhy a window failsUse instead
subarray sum equals k, negatives allowedadding or removing an element can move the sum either wayprefix sums and a hash map of counts: O(n)
shortest subarray with sum at least K, negatives allowedshrinking can raise the sumprefix sums and a monotone deque of starts: O(n)
largest sum of any subarrayno length or limit to hold the window toKadane's best-ending-here scan: O(n)
longest subsequence with some propertythe answer is not contiguousdynamic programming or two pointers on a sorted copy
exactly k of somethingneither shrinking nor growing preserves itexactly(k) = atMost(k) − atMost(k − 1), two windows

Prefix sums turn runs into pairs

With P[0] = 0 and P[j] the sum of the first j elements, the run from i to j − 1 sums to P[j] − P[i]. A question about runs becomes a question about pairs of prefix sums, and pairs do not care about the sign of the elements. "Sum exactly k" asks, for each j, how many earlier i have P[i] = P[j] − k: a hash map of counts. "Shortest with sum at least K" asks for the latest i with P[i] ≤ P[j] − K, and a deque of starts with increasing prefix finds it in O(1) amortised.

The shortest run of [2, −1, 2] with sum at least 3. A window drops the 2 at the front too early; the prefix deque keeps start 0 alive.

  1. Step 1 / 5
    nums
    20-1122
    P
    00211233

    Prefix sums: P = [0, 2, 1, 3]. The subarray i..j−1 sums to P[j] − P[i]. Note that the plain window would drop the 2 at the front once it saw the sum 1 fall short, and miss the answer.

  2. Step 2 / 5
    P
    00j211233
    best—

    j = 0. Nothing reaches K yet. Candidate starts: [0].

  3. Step 3 / 5
    P
    0021j1233
    best—

    j = 1. Nothing reaches K yet. Candidate starts: [0, 1].

  4. Step 4 / 5
    P
    002112j33
    best—

    j = 2. P[2] = 1 is no larger than P at 1, so drop that start. Candidate starts: [0, 2].

  5. Step 5 / 5
    P
    00211233j
    best3

    j = 3. P[3] − P[0] = 3 ≥ 3: length 3, retire start 0. Candidate starts: [2, 3].

TimeO(n)
SpaceO(n)

Both prefix methods need O(n) memory where a window needs O(1). That is the price of handling negative numbers.

A minute to decide

  1. Is the answer contiguous? If not, this chapter is the wrong one.
  2. Can elements be negative, and is the question about a sum? Then think prefix sums first.
  3. Does validity survive shrinking or growing? Shrinking: longest or count with hi − lo + 1. Growing: shortest or count with lo. Neither: try exactly = atMost − atMost, or a different method.
  4. Is the window's length fixed? Then it is the simplest shape, and the only question is the state.

If you have been asked for the sum of every window of length k with negatives allowed, that is still a fixed window: a fixed length needs no monotone property, only an update.

Every problem in this chapter