Binary Subarrays With Sum
Given a binary array nums and an integer goal, count the number of non-empty subarrays whose sum equals goal.
- 1 <= nums.length <= 3 * 10⁴
- nums[i] is either 0 or 1.
- 0 <= goal <= nums.length
Intuition
Binary subarrays with sum counts subarrays of a binary array whose elements total exactly goal. Checking every subarray is O(n²), and two different linear techniques improve on it.
The prefix sum with a hash map approach is the general one. A subarray ending at index i has sum goal precisely when some earlier prefix equals currentSum − goal. Count how many times each prefix sum has been seen and add the matching count as you scan:
- Seed the map with {0: 1}, so a prefix that equals goal on its own is counted.
Omitting that seed loses every subarray starting at index 0 — the single most common bug in the whole prefix-sum family.
The sliding window approach exploits the fact that the array is binary, so all values are non-negative and prefix sums never decrease. A window's sum is then monotonic, which makes windowing valid. But an exact-sum window cannot be counted directly, because leading zeros make many windows share the same sum.
The trick is to count at most instead of exactly. A window with sum at most k is easy to slide, and:
exactly(goal) = atMost(goal) − atMost(goal − 1)
That subtraction is the whole technique, and it recurs across the sliding-window family — Subarrays with K Different Integers uses the same identity.
The hash-map version generalises to arrays with negative numbers; the window version does not, but uses O(1) space.
Counting binary subarrays with sum k rests on one identity: "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
Before reading on: price up what the brute force costs here, then ask what running total makes each query a single subtraction. Aim for O(n) time and O(1) space.
Reframe with prefix sums
A subarray ending at i sums to goal when an earlier prefix equals currentSum - goal. This converts a subarray search into a lookup, removing the inner loop.
Seed the map with zero
Initialise the count map with {0: 1}. Without it, every subarray starting at index 0 is missed — the most common bug in prefix-sum counting.
Scan and accumulate
At each index, add the running sum, add map[sum - goal] to the answer, then record the current sum. Order matters: look up before inserting, so a subarray of length zero is never counted.
Consider the sliding-window alternative
A binary array has no negatives, so prefix sums never decrease and a window's sum is monotonic. That monotonicity is what makes windowing valid here and fails on arrays with negative values.
Count at most, not exactly
Leading zeros make many windows share a sum, so exact counting fails. Count windows with sum at most k instead — that quantity slides cleanly.
Subtract to get the exact count
exactly(goal) = atMost(goal) - atMost(goal - 1). This identity is the whole sliding-window technique and recurs in Subarrays with K Different Integers.
Cost of each approach
Both run in O(n) time. The hash map uses O(n) space and tolerates negative values; the window uses O(1) space but relies on non-negativity.
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.