Binary Subarrays With Sum: Prefix Sum Counting

LeetCode 930 asks: given a binary array nums (containing only 0s and 1s) and an integer goal, return the number of non-empty subarrays with a sum equal to goal. For example, with nums = [1, 0, 1, 0, 1] and goal = 2, the answer is 4.

Why this problem matters

This problem is a gateway to the prefix sum plus hash map pattern, one of the most versatile tools for subarray counting. Once you internalize this technique, you can apply it to dozens of similar problems: counting subarrays with a specific sum, finding contiguous segments with equal 0s and 1s, or checking for subarrays divisible by k. The binary constraint here makes it a gentler introduction to the pattern.

The brute force approach

The most direct approach checks every possible subarray and counts those with the target sum:

def numSubarraysWithSum(nums, goal):
    count = 0
    n = len(nums)
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += nums[j]
            if current_sum == goal:
                count += 1
            elif current_sum > goal:
                break  # optimization: binary array sums only increase
    return count

This runs in O(n^2) time in the worst case. The early break helps when goal is small, but for large arrays this is too slow.

The key insight

Here is the core idea: if you maintain a running prefix sum and track how many times each prefix sum value has appeared, you can count valid subarrays in one pass.

If prefix[j] - prefix[i] == goal, then the subarray from index i+1 to j sums to goal. So at each position j, you just need to know how many earlier positions had prefix[i] == prefix[j] - goal. A hash map gives you that count in O(1).

Walking through it step by step

The optimized solution

from collections import defaultdict

def numSubarraysWithSum(nums, goal):
    count = 0
    prefix = 0
    freq = defaultdict(int)
    freq[0] = 1
    for num in nums:
        prefix += num
        count += freq[prefix - goal]
        freq[prefix] += 1
    return count

Here is how each piece works:

1. prefix accumulates the running sum as we iterate through the array.
2. freq maps each prefix sum value to the number of times it has occurred.
3. We seed freq[0] = 1 because a prefix sum of 0 (before any element) means any subarray starting at index 0 can be counted.
4. At each step, freq[prefix - goal] tells us how many earlier indices had a prefix sum that, when subtracted from the current prefix, equals goal.
5. After checking, we record the current prefix sum in freq.

Complexity analysis

Since the array is binary, prefix sums range from 0 to n. In practice the map holds at most n+1 entries.

Building blocks

1. Prefix sum counting

def prefix_sum_template(nums, target):
    """Count subarrays summing to target using prefix sums."""
    count = 0
    prefix = 0
    freq = {}
    freq[0] = 1
    for num in nums:
        prefix += num
        complement = prefix - target
        count += freq.get(complement, 0)
        freq[prefix] = freq.get(prefix, 0) + 1
    return count

The template works for any target sum, not just binary arrays. You accumulate a running total, look up the complement in your frequency map, and increment the count.

2. Hash map for complement lookup

def complement_lookup(freq_map, current_prefix, goal):
    """Look up how many prior prefixes would form a valid subarray."""
    complement = current_prefix - goal
    return freq_map.get(complement, 0)

This is the same "two-sum" idea applied to prefix sums. Instead of finding two numbers that add to a target, you find two prefix sums whose difference equals the target.

Edge cases

• goal = 0: Subarrays of consecutive zeros all sum to 0. The prefix sum stays constant across these stretches, and the frequency map correctly counts all pairs of equal prefix sums.
• All ones: Every subarray of length goal is valid. The answer equals n - goal + 1.
• All zeros with goal = 0: Every non-empty subarray sums to 0. The answer is n * (n + 1) / 2.
• goal larger than array length: Impossible to achieve, so the answer is 0.
• Single element: If nums = [1] and goal = 1, the answer is 1. If goal = 0, the answer is 0.

From understanding to recall

Reading through this solution once gives you understanding, but that understanding fades within days. The prefix sum counting pattern shows up repeatedly in interview settings, and the difference between "I've seen this before" and "I can implement this in five minutes" comes down to practice.

Spaced repetition bridges that gap. By revisiting this problem at increasing intervals, you move the pattern from short-term memory into long-term recall. Each review takes less time than the last, and eventually the technique becomes automatic.

CodeBricks schedules these reviews for you, surfacing problems right before you would forget them. Instead of grinding hundreds of problems, you reinforce the patterns you have already learned at the optimal moment.

Related posts

• Subarray Sum Equals K - The general version of prefix sum counting for any target sum
• Contiguous Array - Prefix sum technique applied to equal 0s and 1s
• Continuous Subarray Sum - Prefix sum with modular arithmetic

The prefix sum plus hash map combination is one of those patterns that unlocks an entire category of problems. Once you can recognize "count subarrays with property X" as a signal for this approach, you will solve these problems quickly and confidently. CodeBricks helps you build that recognition through deliberate, spaced practice.