Binary Subarrays With Sum
Count the non-empty subarrays of a binary array whose sum equals goal, by counting sums at most goal and at most goal - 1 with two sliding windows.
Problem Understanding
Binary Subarrays With Sum: given a binary array nums and an integer goal, return the number of non-empty contiguous subarrays whose sum is goal.
Examples: [1,0,1,0,1], goal 2 → 4; [0,0,0,0,0], goal 0 → 15.
The Intuition: Exactly = At Most − At Most
Counting "sum at most g" is a textbook sliding window: grow on the right, shrink on the left while the sum is too big, and every window ending at right inside the current one counts. Then:
- atMost(goal) counts subarrays with sum 0, 1, …, goal.
- atMost(goal − 1) counts sum 0, 1, …, goal − 1.
- The difference is exactly the subarrays with sum goal.
The same shrink-while-invalid window drives Max Consecutive Ones III, and the prefix-sum alternative is Subarray Sum Equals K.
Interactive Walkthrough
GOAL 2 · atMost(2) − atMost(1)
EXACTLY = AT MOST − AT MOST
pass 1: sum ≤ 2
0
1
2
3
4
sum
:
count
:
answer
:
Exactly 2 = (subarrays with sum ≤ 2) − (subarrays with sum ≤ 1)
Next
atMost(2): count subarrays whose sum is at most 2
nums
goal
The run makes two passes. On each count step the shaded window is exactly the set of starting points counted for subarrays ending at R. Try Example 2 to see atMost(−1) return 0.
Dry Run Table
Input: [1,0,1,0,1], goal 2.
| Pass | Counts per right | Total |
|---|---|---|
| atMost(2) | 1, 2, 3, 4, 4 | 14 |
| atMost(1) | 1, 2, 2, 3, 2 | 10 |
Answer: 14 − 10 = 4.
The Solution Template
A helper for at most g, called twice.
Binary Subarrays With Sum Code
1var numSubarraysWithSum = function(nums, goal) {2 const atMost = (g) => {3 if (g < 0) return 0;4 let left = 0, sum = 0, count = 0;5 for (let right = 0; right < nums.length; right++) {6 sum += nums[right];7 while (sum > g) sum -= nums[left++];8 count += right - left + 1;9 }10 return count;11 };12 return atMost(goal) - atMost(goal - 1);13};
Edge Cases & Common Mistakes
- goal = 0: atMost(−1) must return 0, not loop forever.
- goal larger than the total: both passes count everything; the answer is 0.
- All zeros: every subarray has sum 0: n(n + 1) / 2.
- Counting only when sum == goal: misses windows that differ only by zeros.
- Negative numbers: the window method breaks; use prefix sums instead.
Summary
Count subarrays with sum at most g using a shrinking window that adds right − left + 1 per step, and return atMost(goal) − atMost(goal − 1). O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet