Binary Subarrays With Sum

1. Define the problem

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum equal to goal . Count subarrays with sum at most goal, then subtract the count with sum at most goal minus one — the difference isolates subarrays whose sum is exactly goal, using a variable-size window helper applied twice.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
nums_i is either 0 or 1
0 ≤ goal ≤ nums.length

Example

Inputnums = [1, 0, 1, 0, 1], goal = 2

Output4

Explanation Four subarrays sum to 2: [1,0,1] (indices 0-2), [1,0,1,0] (0-3), [0,1,0,1] (1-4), and [1,0,1] (2-4).

2. Visualize the solution

Count-at-most(goal) minus count-at-most(goal-1)

Statusgrow

Window [1,0,1] sum = 2 <= 2; add 3 to the running count.

What happens in this step

atMost(2) pass — window = [0, 2]  [1, 0, 1]

before: sum = 1 (right = 1), count = 3
  add nums[2] = 1 → sum = 2

sum 2 ≤ target 2 — window valid; add its length (right − left + 1 = 3) to count → count = 3 + 3 = 6.

Step 1 of 4

Steps to visualize

Run a variable window that counts subarrays with sum at most a target.
Grow right and add each value into a running sum.
While the sum exceeds the target, shrink from the left.
At each right position, add the current window size to the count.
Call this helper for goal and for goal minus one, then subtract.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Count-at-most(goal) minus count-at-most(goal-1)

Statusgrow

Window [1,0,1] sum = 2 <= 2; add 3 to the running count.

What happens in this step

atMost(2) pass — window = [0, 2]  [1, 0, 1]

before: sum = 1 (right = 1), count = 3
  add nums[2] = 1 → sum = 2

sum 2 ≤ target 2 — window valid; add its length (right − left + 1 = 3) to count → count = 3 + 3 = 6.

Step 1 of 4

4. Solution

Solution

solution.tsTypeScript

function numSubarraysWithSum(nums, goal) {
  function atMost(k) {
    if (k < 0) return 0;
    let left = 0;
    let sum = 0;
    let count = 0;

    for (let right = 0; right < nums.length; right++) {
      sum += nums[right];
      while (sum > k) {
        sum -= nums[left];
        left++;
      }
      count += right - left + 1;
    }

    return count;
  }

  return atMost(goal) - atMost(goal - 1);
}

Time: O(n)
Space: O(1)

5. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 0, 1, 0, 1], goal = 2`	`4`	Docstring example
`nums = [0, 0, 0, 0], goal = 0`	`10`	goal = 0 counts every run of pure zeros
`nums = [1, 1, 1], goal = 2`	`2`	All ones
`nums = [1], goal = 1`	`1`	Single element matching goal
`nums = [0], goal = 1`	`0`	Single element that cannot reach goal
`nums = [0, 0, 0], goal = 1`	`0`	All zeros with a positive goal
`nums = [0, 0, 1, 0, 0], goal = 1`	`9`	Single 1 with many left/right boundary choices

Binary Subarrays With Sum