When a sliding window does not work

Sliding window Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
nums, k = [1, -1, 1], 1
prefix, seen, count = 0, {0: 1}, 0
for x in nums:
    prefix += x
    count += seen.get(prefix - k, 0)
    seen[prefix] = seen.get(prefix, 0) + 1
print(count)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3

Right: [1], [1] at the end, and [1, -1, 1] each sum to 1.

A window would miss the full list because shrinking on the negative value is not monotonic; prefix counts find every run.

Why not the others?
  • B 2. The whole list also sums to 1.
  • C 1. Two single-item runs and the full list all count.

30-second answer

Shrinking from the left is only safe if dropping an item always moves the total in one direction. With negative numbers, dropping an item can raise the total, so a window that is too big might become valid by growing. Use prefix sums instead: a run from i to j sums to prefix[j] - prefix[i], and a hash map of earlier prefixes finds matching starts in O(n).

Practise saying it · 60 s. No recording, just a timer

Explain why negatives break the window and what replaces it.

Say your answer out loud, then check which of these points you covered:

  • Shrinking is not monotonic
  • Prefix sums
  • Hash map of earlier prefixes

Deep dive

Counting runs that sum to exactly k with negatives: map each prefix sum to how many times it appeared.

Longest run with sum at most k and negatives: prefix sums plus a sorted structure or a monotonic stack, O(n log n).

Spotting this early saves an interview: ask whether values can be negative before choosing a window.

Common mistakes

  • Applying the positive-number window to data that includes refunds or losses.
  • Assuming 'contiguous' always means sliding window.

Senior take & follow-ups

Ask about negative values before you start. It is a cheap question that shows you know the limit of the pattern.

Follow-up questions

Think of your answer first, then open the hint.

  1. How do prefix sums handle 'sum exactly k'?

    Show hint

    For each prefix p, add the count of earlier prefixes equal to p - k.

  2. What about the largest-sum run?

    Show hint

    Kadane's algorithm: keep the best sum ending here, O(n).

What each operation costs: Arrays · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.