Binary Subarrays With Sum
Problem Statement
Given a binary array nums and an integer goal, return the number of non-empty contiguous subarrays whose sum is exactly goal.
Input
A binary integer array nums and an integer goal, the exact sum each valid subarray must have.
Output
An integer: the number of contiguous subarrays with sum exactly goal.
Constraints
- •
1 <= nums.length <= 3 * 10^4 - •
nums[i] is either 0 or 1 - •
0 <= goal <= nums.length
Examples
Example 1
nums = [1,0,1,0,1], goal = 2
4Example 2
nums = [0,0,0,0,0], goal = 0
15Example 3
nums = [1,1,1], goal = 2
2Learning Objectives
- Recognise exact binary-sum counting as another form of **exactly(K) = atMost(K) - atMost(K - 1)**.
- Use a variable window because binary values are non-negative and the window sum shrinks monotonically from the left.
- Handle **goal = 0** correctly by returning **0** for **atMost(-1)**.
- Explain how zeros create many valid suffixes from one right edge.
Intuition
Pattern Identification
The array is binary, so every element is non-negative. That makes sum <= limit a monotone window condition: expanding right can only increase or preserve the sum, and shrinking left can only decrease or preserve it.
Counting subarrays with sum exactly goal directly is possible with prefix sums, but the advanced sliding-window pattern is cleaner here: count subarrays with sum at most goal, subtract those with sum at most goal - 1, and the remaining subarrays must have sum exactly goal. The guard for negative limits is essential because goal may be 0.
Common mistakes
- ×Forgetting the negative-limit guard, which breaks cases where **goal = 0**.
- ×Using this at-most sum trick on arrays with negative numbers, where the monotone window property no longer holds.
- ×Adding only one valid subarray per right edge instead of **right - left + 1**.
- ×Shrinking while **sum >= limit** instead of only while **sum > limit**, which removes valid windows whose sum equals the limit.
Algorithm Explanation
Window setup
Build atMost(limit) for binary sums. Track left, windowSum, and total. After adding nums[right], shrink from the left while windowSum > limit. When the window is valid, every suffix ending at right also has sum at most limit, because removing leading binary values cannot increase the sum.
Window visualization
For nums = [1,0,1,0,1] and limit = 2, at right = 3 the window [1,0,1,0] has sum 2. The four suffixes ending there all have sum at most 2, so this step adds 4. At right = 4, adding another 1 makes the sum 3. Shrink past the leftmost 1; the valid window becomes [0,1,0,1], so this step adds 4 more.
Algorithm
- Return 0 from atMost(limit) when limit < 0.
- Expand right through the array and add nums[right] to windowSum.
- While windowSum > limit, subtract nums[left] and move left forward.
- Add right - left + 1 to the helper count.
- The final answer is atMost(goal) - atMost(goal - 1).
Solutions
Solution: At-most difference on binary sum
Because all values are 0 or 1, the at-most sum condition is monotone and supports a standard variable window. The helper counts all subarrays with sum no larger than a target, and subtraction isolates exactly the requested sum.
Step-by-step
- Compute the number of subarrays with sum at most goal.
- Compute the number of subarrays with sum at most goal - 1.
- In each helper pass, expand right and shrink left only while the sum is too large.
- Add the valid suffix count right - left + 1 after every right edge.
- Return the difference between the two helper counts.
O(n)
O(1)
Two linear helper passes are still O(n), and the window stores only counters and pointers.
Java implementation
Dry Run
Sample input
nums = [1,0,1,0,1], goal = 2. Count atMost(2) and atMost(1), then subtract to isolate sum exactly 2.
| phase | right | value | left after shrink | window sum | subarrays added | running count | meaning |
|---|---|---|---|---|---|---|---|
| atMost(2) | 0 | 1 | 0 | 1 | 1 | 1 | [1] |
| atMost(2) | 1 | 0 | 0 | 1 | 2 | 3 | zero keeps both suffixes valid |
| atMost(2) | 2 | 1 | 0 | 2 | 3 | 6 | sum reaches the limit |
| atMost(2) | 3 | 0 | 0 | 2 | 4 | 10 | four suffixes are valid |
| atMost(2) | 4 | 1 | 1 | 2 | 4 | 14 | shrink past the first one |
| atMost(1) | 0 | 1 | 0 | 1 | 1 | 1 | single one allowed |
| atMost(1) | 1 | 0 | 0 | 1 | 2 | 3 | leading zero adds another suffix |
| atMost(1) | 2 | 1 | 1 | 1 | 2 | 5 | remove the first one |
| atMost(1) | 3 | 0 | 1 | 1 | 3 | 8 | zero extends all valid suffixes |
| atMost(1) | 4 | 1 | 3 | 1 | 2 | 10 | remove zero then one until valid |
The helper counts are atMost(2) = 14 and atMost(1) = 10. The difference is 4, exactly the number of subarrays whose binary sum is 2.
Interview Tips
Mention both accepted viewpoints: prefix sums with a hash map and sliding window using atMost. For this course, emphasize why sliding window is legal: the values are binary, so the sum condition is monotone. If the interviewer changes the array to include negative values, switch to prefix sums because the window invariant no longer behaves monotonically.
Likely follow-ups
- How would you solve the same problem if **nums** could contain negative numbers?
- How would the code change if the array contained only non-negative values, not just binary values?
- Can you derive the same answer with prefix sums and a frequency map?
- Why does **goal = 0** require special care in the at-most helper?
Similar Problems
Key Takeaways
- Binary arrays make **sum <= limit** a monotone sliding-window invariant.
- Exact sum can be counted as **atMost(goal) - atMost(goal - 1)**.
- Zeros matter because they create multiple valid suffixes without increasing the sum.
- The negative-limit guard makes **goal = 0** work naturally.