Debugging challengeIntermediate

Sliding window on subarray sum equals k

Scenario

This function should count contiguous subarrays whose sum equals k. It passes all tests with positive numbers but returns 2 for nums = [1, -1, 1, -1], k = 0 — the correct answer is 4 ([1,-1], [-1,1], [1,-1] and [1,-1,1,-1]). Explain why and fix it.

Broken
1def count_subarrays(nums, k):
2 count = 0
3 left = 0
4 window = 0
5 for right, x in enumerate(nums):
6 window += x
7 while window > k and left <= right:
8 window -= nums[left]
9 left += 1
10 if window == k:
11 count += 1
12 return count

The corrected version appears here once you have revealed everything below.

Your task

  1. State the property of the input that the sliding window relies on and show which line encodes it.
  2. Trace [1, -1, 1, -1], k = 0 and show a valid subarray the window skips.
  3. Explain why no two-pointer scheme can be correct here, regardless of tweaks.
  4. Give the correct O(n) algorithm and its space cost.
  5. List edge cases: k = 0, all zeros, the empty prefix.
DebuggingPattern RecognitionSystematic Reasoning

Work it out

Write your analysis before revealing anything. The self-check below compares it against what a strong answer contains.

Reveal

Progressive — each section builds on the previous one.

The bug
Why it happens
The fix
Edge cases
Complexity
What this tests

Self-check

Tick what your analysis covered. Be honest — this feeds your readiness profile.

0/7

Related concepts