LeetCode 930: Binary Subarrays With Sum

Problem Restatement

We are given a binary array nums and an integer goal.

A binary array means every value is either:

0

or:

1

We need to count how many non-empty contiguous subarrays have sum exactly equal to goal.

A subarray must be continuous. We cannot skip elements.

The official statement asks for the number of non-empty subarrays whose sum is goal, where nums is binary. Example cases include [1,0,1,0,1] with goal = 2, which returns 4, and [0,0,0,0,0] with goal = 0, which returns 15.

Input and Output

Function shape:

class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        ...

Examples

Example 1:

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

The valid subarrays are:

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

There are 4 valid subarrays.

So the answer is:

4

Example 2:

nums = [0, 0, 0, 0, 0]
goal = 0

Every non-empty subarray has sum 0.

There are:

5 + 4 + 3 + 2 + 1 = 15

valid subarrays.

So the answer is:

15

First Thought: Check Every Subarray

The direct way is to try every starting index and every ending index.

For each start:

1. Keep a running sum.
2. Extend the end index one step at a time.
3. Count the subarray when the running sum equals goal.

Code:

class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        n = len(nums)
        ans = 0

        for left in range(n):
            total = 0

            for right in range(left, n):
                total += nums[right]

                if total == goal:
                    ans += 1

        return ans

This is correct, but it checks too many subarrays.

There are O(n^2) subarrays, so this is too slow for large input.

Key Insight

We can use prefix sums.

Let:

prefix[i]

be the sum of the first i elements.

The sum of a subarray from left to right is:

prefix[right + 1] - prefix[left]

We want this to equal goal.

So:

prefix[right + 1] - prefix[left] = goal

Rearrange:

prefix[left] = prefix[right + 1] - goal

This means that when we are at the current prefix sum, we only need to know how many earlier prefix sums equal:

current_sum - goal

A hash map can store how many times each prefix sum has appeared.

Algorithm

Create a map:

count = {0: 1}

This means we have seen prefix sum 0 once before reading any element.

Then scan nums.

For each number:

1. Add it to current.
2. Compute need = current - goal.
3. Add count[need] to the answer.
4. Add the current prefix sum to the map.

The order matters.

We count earlier prefix sums before inserting the current prefix sum.

Walkthrough

Use:

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

Start:

count = {0: 1}
current = 0
ans = 0

The final answer is:

4

The last step adds 2 because prefix sum 1 appeared twice earlier. Each earlier prefix sum gives one valid subarray ending at the current index.

Correctness

The algorithm maintains a frequency map of all prefix sums seen before the current position.

At a current index, let the current prefix sum be current.

A subarray ending at this index has sum goal exactly when its starting prefix sum is:

current - goal

The map tells us how many earlier positions have that prefix sum. Each such earlier position defines one distinct subarray ending at the current index with sum goal.

The algorithm adds exactly that number to the answer.

Then it records the current prefix sum so it can be used by future subarrays.

Every valid subarray has one ending index. When the scan reaches that ending index, the subarray’s starting prefix sum is already in the map, so the subarray is counted.

No invalid subarray is counted, because the algorithm only adds prefixes that satisfy:

current - earlier_prefix = goal

Therefore, the final answer is exactly the number of non-empty subarrays with sum goal.

Complexity

Implementation

from collections import defaultdict

class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        count = defaultdict(int)
        count[0] = 1

        current = 0
        ans = 0

        for num in nums:
            current += num

            need = current - goal
            ans += count[need]

            count[current] += 1

        return ans

Code Explanation

We use a map from prefix sum to frequency:

count = defaultdict(int)
count[0] = 1

The initial 0 handles subarrays that start at index 0.

For example, if the current prefix sum is already equal to goal, then:

current - goal == 0

So the initial prefix sum contributes one valid subarray.

We update the running prefix sum:

current += num

Then we find the prefix sum needed to form a subarray with sum goal:

need = current - goal

Every earlier occurrence of need gives one valid subarray ending here:

ans += count[need]

Finally, we record the current prefix sum:

count[current] += 1

Testing

def run_tests():
    s = Solution()

    assert s.numSubarraysWithSum([1, 0, 1, 0, 1], 2) == 4
    assert s.numSubarraysWithSum([0, 0, 0, 0, 0], 0) == 15
    assert s.numSubarraysWithSum([1, 1, 1], 2) == 2
    assert s.numSubarraysWithSum([1, 0, 0, 1], 1) == 6
    assert s.numSubarraysWithSum([0], 0) == 1
    assert s.numSubarraysWithSum([1], 0) == 0

    print("all tests passed")

run_tests()