Binary Subarrays With Sum
Given a binary array nums and an integer goal, count the number of non-empty subarrays whose sum equals goal.
Intuition
Counting subarrays with sum exactly goal is awkward, but counting subarrays with sum at most k slides cleanly. Then exactly(goal) = atMost(goal) − atMost(goal − 1).
"Exactly k" = "at most k" − "at most k−1". A sliding window can't directly count subarrays summing to exactly a value, because the shrink condition isn't monotonic — but at most is, so solve the easy version twice and subtract. This decomposition works for any counting problem with a monotone "at most" variant.
Approach
Counting exact sums directly is awkward
Brute force sums every subarray and tallies the ones equal to goal — O(n²). A sliding window seems natural, but it struggles with exact sums: when the window sum equals the goal, you can't simply decide whether to grow or shrink, because a 0 at either edge keeps the sum the same. The window technique wants a monotonic condition.
Reframe 'exactly' as a difference of 'at most'
The clean, monotonic version is atMost(k) = the number of subarrays whose sum is ≤ k — that does slide nicely. Then the answer is atMost(goal) − atMost(goal − 1): every subarray summing to ≤ goal, minus every subarray summing to ≤ goal−1, leaves precisely those summing to exactly goal. Trading one hard count for two easy ones is the whole trick.
Implement atMost as a standard window
For atMost(k): expand right, adding to a running sum; whenever the sum exceeds k, shrink from left until it's valid again. At each right, every subarray ending there and starting anywhere in [left, right] is valid, contributing right − left + 1 to the count. Call it twice and subtract. Two linear passes — O(n) time, O(1) space.
Solution & live demo
Common pitfalls
Trying to slide for exactly k
while total > goal:
total -= nums[left]; left += 1
if total == goal: count += 1return at_most(goal) - at_most(goal - 1)
With zeros in the array, many windows share the same sum and a single window position corresponds to several valid subarrays. The window can't enumerate them; the at-most difference counts them all correctly.
Omitting the negative guard
def at_most(k):
left = total = count = 0def at_most(k):
if k < 0:
return 0When goal is 0, the second call passes -1. The while loop then shrinks the window past right, producing a negative count that corrupts the subtraction. Zero subarrays have a sum of at most −1, so returning 0 is both correct and necessary.
Counting one per window instead of right - left + 1
count += 1
count += right - left + 1
Every subarray ending at right and starting anywhere from left onwards satisfies the at-most condition — that's right - left + 1 of them, not one. Counting singly undercounts by a large factor.
Edge cases
atMost(-1) returns 0, so the answer is atMost(0) — runs of consecutive zeros, counted correctly.
Only the full array qualifies; the window math yields exactly 1.
The two atMost counts are equal, so their difference is 0.