AlgoViz
HomeSliding Window

Binary Subarrays With Sum

Hard

At most goal, minus at most goal-1

Problem

Count subarrays of a binary array whose sum equals goal.

In simple words

Count running sums; each time current-minus-goal was seen, that many subarrays end here with the goal.

The idea

Counting subarrays with a sum of exactly goal is awkward for a window, but counting those with at most goal is easy. Exactly goal is then atMost(goal) - atMost(goal - 1), which reduces the problem to running the same helper twice.

The trick

  • exactly(k) = atMost(k) - atMost(k-1) — a pattern worth memorising.
  • In atMost, each new right edge adds (right - left + 1) subarrays.
  • A prefix-sum count map solves it in one pass too.
1
0
1
0
1
0
1
2
3
4
target2

Step 1 of 17. Brute force: add up every subarray, count those summing to 2. Values: 1, 0, 1, 0, 1. target 2.

1/17
Brute force
timeO(n²)spaceO(1)

Every subarray.

1for (let i = 0; i < n; i++) {2  let sum = 0;3  for (let j = i; j < n; j++) { sum += nums[j]; if (sum === goal) count++; }4}

Input

array
[1, 0, 1, 0, 1]

Memory

target
2

Output

count
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 0, 1, 0, 1], goal = 2
Output:
4
Explanation:
4 subarrays add up to 2.

Example 2

Input:
nums = [0, 0, 0, 0, 0], goal = 0
Output:
15
Explanation:
Many all-zero windows sum to 0.

Example 3

Input:
nums = [1, 1, 1], goal = 2
Output:
2
Explanation:
Two neighbouring 1-pairs → 2.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.