LeetCode 930 - Binary Subarrays With Sum

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window, Prefix Sum

Solution

Problem Understanding

The problem asks us to count the number of contiguous subarrays in a binary array nums whose sum equals a given integer goal. A binary array only contains 0s and 1s. A subarray is any contiguous sequence of elements in the array, meaning that order matters and elements cannot be skipped.

The input nums represents the sequence of binary values, and goal represents the target sum we want from subarrays. The output is an integer representing the total number of subarrays whose sum is exactly equal to goal.

The constraints tell us that nums can be fairly large, up to 3 * 10^4 elements, and the values are strictly 0 or 1. The goal can range from 0 to the length of nums. This means that a naive approach that checks all possible subarrays will be too slow, as the number of subarrays grows quadratically with the array length.

Important edge cases include an array full of zeros, a goal of zero, a goal equal to the length of the array, or a mixture of zeros and ones where multiple overlapping subarrays sum to the goal. The problem guarantees that the array contains only binary values, so we do not need to handle negative numbers or non-integer inputs.

Approaches

The brute-force approach iterates over all possible subarrays and sums them to see if they equal goal. This is correct because it explicitly checks every combination, but it is too slow for large inputs due to its O(n²) time complexity.

The optimal approach uses a prefix sum combined with a hash map to count occurrences. The key insight is that if the sum of elements from the start to index i is current_sum and the sum of elements from the start to some earlier index j is current_sum - goal, then the subarray from j+1 to i sums to goal. By storing counts of prefix sums in a hash map, we can determine in constant time how many valid subarrays end at the current index.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Iterate over all subarrays and sum them individually
Optimal	O(n)	O(n)	Use prefix sum and hash map to count subarrays efficiently

Algorithm Walkthrough

Initialize a hash map prefix_count with a single entry {0:1} to represent the sum zero occurring once before starting.
Initialize current_sum to 0. This will track the sum of elements up to the current index.
Initialize result to 0. This will accumulate the number of subarrays that sum to goal.
Iterate through each element num in nums.
Add num to current_sum.
Compute current_sum - goal. If this value exists in prefix_count, it means there are that many subarrays ending at the current index which sum to goal.
Add the count from the hash map to result.
Increment the count of current_sum in prefix_count by 1. If it does not exist, initialize it to 1.
Return result after processing all elements.

Why it works: The invariant is that prefix_count always stores the number of times each prefix sum has occurred. For any ending index i, the number of valid starting indices j where the subarray sums to goal is exactly prefix_count[current_sum - goal]. This ensures we count all subarrays correctly without missing overlaps.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1
        current_sum = 0
        result = 0
        
        for num in nums:
            current_sum += num
            if (current_sum - goal) in prefix_count:
                result += prefix_count[current_sum - goal]
            prefix_count[current_sum] += 1
        
        return result

The Python implementation uses a defaultdict to store counts of prefix sums, allowing us to increment counts without checking for existence. We iterate through the array once, updating current_sum and using the map to count valid subarrays. The if check ensures we only add to result when a valid prefix sum exists.

Go Solution

func numSubarraysWithSum(nums []int, goal int) int {
    prefixCount := make(map[int]int)
    prefixCount[0] = 1
    currentSum := 0
    result := 0

    for _, num := range nums {
        currentSum += num
        if count, exists := prefixCount[currentSum - goal]; exists {
            result += count
        }
        prefixCount[currentSum]++
    }
    
    return result
}

The Go solution mirrors the Python logic. We use a map to store prefix sums and check for existence using the exists boolean. Incrementing map values is straightforward, and the iteration logic is identical.

Worked Examples

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

Index	num	current_sum	current_sum-goal	prefix_count	result
0	1	1	-1	{0:1,1:1}	0
1	0	1	-1	{0:1,1:2}	0
2	1	2	0	{0:1,1:2,2:1}	1
3	0	2	0	{0:1,1:2,2:2}	2
4	1	3	1	{0:1,1:2,2:2,3:1}	4

Output: 4

Example 2: nums = [0,0,0,0,0], goal = 0

Each zero can start a subarray summing to 0. Using the prefix count logic, all combinations of contiguous zeros are counted, yielding output 15.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the array once, performing constant time operations per element
Space	O(n)	The prefix sum hash map may store up to n+1 different sums in the worst case

The optimal approach leverages the fact that prefix sums combined with a hash map allow us to find subarrays summing to goal efficiently, avoiding the quadratic cost of checking all subarrays individually.

Test Cases

# Basic examples
assert Solution().numSubarraysWithSum([1,0,1,0,1], 2) == 4  # Provided example 1
assert Solution().numSubarraysWithSum([0,0,0,0,0], 0) == 15  # Provided example 2

# Edge cases
assert Solution().numSubarraysWithSum([1,1,1,1], 0) == 0  # No subarray sums to 0
assert Solution().numSubarraysWithSum([1,1,1,1], 4) == 1  # Entire array sums to goal
assert Solution().numSubarraysWithSum([1,0,0,1,0,1], 2) == 6  # Mixed zeros and ones

# Single element arrays
assert Solution().numSubarraysWithSum([0], 0) == 1
assert Solution().numSubarraysWithSum([1], 1) == 1
assert Solution().numSubarraysWithSum([1], 0) == 0

Test	Why
[1,0,1,0,1], 2	Standard mixed input, multiple overlapping subarrays
[0,0,0,0,0], 0	All zeros, goal zero, maximal subarray count
[1,1,1,1], 0	Goal zero with no zeros in array
[1,1,1,1], 4	Entire array sums to goal
[1,0,0,1,0,1], 2	Mixed input, overlapping subarrays
Single element arrays	Test minimal input size and edge sum conditions

Edge Cases

Edge Case 1: Goal is zero. When goal is 0, all contiguous subarrays of zeros must be counted. Using the prefix sum approach handles this naturally because the difference current_sum - goal equals current_sum, and prefix sums of 0 are correctly counted.

Edge Case 2: Array full of zeros. Similar to the previous case, multiple overlapping subarrays contribute to the result. Each new zero increases the count of previous zeros in prefix_count, giving the correct total.

Edge Case 3: Single-element arrays. When the array has only one element, the algorithm correctly returns 1 if the element matches goal or 0 otherwise. The prefix sum map initializes with {0:1} to handle this case correctly.

Edge Case 4: Large array. For arrays close to the upper limit of