#930

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Binary Subarrays With Sum

Count all contiguous subarrays in a binary array whose elements sum exactly to a given goal using prefix sums efficiently.

array hash table sliding window prefix sum

Problem Statement

Given a binary array nums and an integer goal, return the number of non-empty contiguous subarrays whose sum equals goal. Each subarray consists of consecutive elements from nums and must sum precisely to goal.

For example, if nums = [1,0,1,0,1] and goal = 2, there are exactly 4 subarrays that satisfy this condition. Constraints ensure nums contains only 0s and 1s, with array length up to 3 * 10^4 and goal between 0 and nums.length.

Examples

Example 1

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

Output: 4

The 4 subarrays are bolded and underlined below: [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1]

Example 2

Input: nums = [0,0,0,0,0], goal = 0

Output: 15

Example details omitted.

Constraints

1 <= nums.length <= 3 * 104
nums[i] is either 0 or 1.
0 <= goal <= nums.length

Solution Approach

Prefix Sum with Hash Map

Iterate through nums while maintaining a cumulative prefix sum. Use a hash map to count occurrences of each prefix sum. For each element, add the number of times (current prefix sum - goal) has occurred to the result.

Sliding Window Not Directly Applicable

A pure sliding window cannot handle zero elements flexibly, as zeros do not increase the sum. The hash-based prefix sum method accounts for zeros naturally, avoiding missed subarrays.

Single Pass Efficiency

Combine the prefix sum and hash counting in one pass. Update the hash map after evaluating each element to ensure all subarrays ending at the current index are counted, maintaining O(n) time and minimal extra space.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The algorithm scans the array once (O(n)) and uses a hash map storing at most n prefix sums, but values are bounded by the cumulative sum range; space remains effectively O(1) for integer keys.

What Interviewers Usually Probe

Checks if you can optimize counting subarrays without nested loops.
May ask why sliding window alone fails when zeros exist.
Looks for clear explanation of prefix sum mapping to goal counts.

Common Pitfalls or Variants

Common pitfalls

Forgetting to initialize prefix sum count map with 0 sum seen once.
Updating hash map before counting current subarrays can undercount.
Misinterpreting zeros and ones leads to missing valid subarrays.

Follow-up variants

Count subarrays with sum less than or equal to goal.
Handle arrays with arbitrary integers, not just binary.
Return all subarrays instead of counting them.

FAQ

What is the key pattern for Binary Subarrays With Sum?

The main pattern is array scanning with prefix sum and hash map lookup to count all subarrays matching the goal sum.

Can a sliding window solve this problem alone?

No, zeros prevent a fixed-length sliding window from capturing all valid subarrays; prefix sums with hash mapping are needed.

How do I handle goal = 0?

Initialize the hash map with 0 sum counted once; this ensures subarrays summing to zero are correctly counted.

What is the time complexity of the optimal solution?

The solution runs in O(n) time with a single pass and maintains prefix sum counts in a hash map.

Are there variants of this problem?

Yes, you can modify it to count subarrays with sum less than or equal to a target or handle arbitrary integer arrays.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        cnt = Counter({0: 1})
        ans = s = 0
        for v in nums:
            s += v
            ans += cnt[s - goal]
            cnt[s] += 1
        return ans

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        cnt = Counter({0: 1})
        ans = s = 0
        for v in nums:
            s += v
            ans += cnt[s - goal]
            cnt[s] += 1
        return ans

Continue Practicing

#1248 count number of nice subarrays #1658 minimum operations to reduce x to zero #995 minimum number of k consecutive bit flips