How do you solve Binary Subarrays With Sum?

Maintain a running prefix sum and a frequency map of prefix sums seen so far. For each new prefix sum, add to the result the count of prefix sums equal to prefixSum - goal. Update the frequency map with the current prefix sum. This single pass counts all subarrays summing to goal efficiently.

What pattern does Binary Subarrays With Sum use?

The Pattern: Prefix Sum (Frequency Counting) The Heuristic: The difference between two prefix sums equals the sum of the subarray between them; by tracking prefix sum frequencies, one can count subarrays with a target sum in linear time without enumerating all subarrays.

Binary Subarrays With Sum — Prefix Sum

Q: What is the time complexity of Binary Subarrays With Sum?

O(n). The algorithm iterates through the array once, performing O(1) operations per element for prefix sum updates and hash map lookups.

Problem

Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum equal to goal.

1 ≤ nums.length ≤ 3 * 10⁴
nums[i] is 0 or 1
0 ≤ goal ≤ nums.length

Example

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

Output: 4

The brute-force approach would check every subarray and sum its elements, resulting in O(n²) time complexity. Instead, the algorithm uses prefix sums and a frequency map to count how many prefix sums have occurred. For each prefix sum, it checks if there exists a prefix sum that is exactly 'goal' less, indicating a subarray summing to goal. For example, iterating through nums: - prefix sums: [1,1,2,2,3] - When prefix sum is 2 at index 2, check if prefix sum 0 (2 - 2) exists; yes, count += freq[0] - This process accumulates counts for all valid subarrays efficiently. The critical insight is that the difference between two prefix sums equals the sum of the subarray between those indices. By tracking frequencies of prefix sums, the algorithm counts all subarrays summing to goal in a single pass.

Approach

Straightforward Solution

A brute-force approach enumerates all subarrays and sums their elements, resulting in O(n²) time complexity, which is too slow for large inputs.

Core Observation

The sum of a subarray equals the difference between two prefix sums. Specifically, sum(nums[i..j]) = prefixSum[j] - prefixSum[i-1]. This means that if we know the frequency of prefix sums, we can count subarrays summing to goal by checking how many prefix sums equal currentPrefixSum - goal.

Path to Optimal

Preview

Recognizing the prefix sum relationship transforms the problem into counting pairs of prefix sums differing by goal. Using a hash map to store frequencies of prefix sums allows constant-time lookups…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Maintain a running prefix sum and a frequency map of prefix sums seen so far. For each new prefix sum, add to the result the count of prefix sums equal to prefixSum - goal…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm iterates through the array once, performing O(1) operations per element for prefix sum updates and hash map lookups.

Space

O(n)

In the worst case, all prefix sums are unique, requiring O(n) space to store their frequencies in the hash map.

Solution

Python

1class Solution:
2    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
3
4        prefix = 0
5        freq = {0: 1}
6        res = 0
7
8        for num in nums:
9            prefix += num
10            res += freq.get(prefix - goal, 0)
11            freq[prefix] = freq.get(prefix, 0) + 1
12
13        return res

Step-by-Step Solution

1

Initialize Prefix Sum and Frequency Map

4prefix = 0
5freq = {0: 1}
6res = 0

Objective

To set up the initial state for prefix sum calculation and frequency tracking.

Key Insight

Starting with prefix sum zero and frequency map containing {0:1} accounts for subarrays that start at index zero and sum exactly to goal. This initialization ensures the algorithm correctly counts subarrays from the beginning without special casing.

Interview Quick-Check

Core Logic

Initializing freq with {0:1} is essential to count subarrays starting at the first element that sum to goal.

Common Pitfalls & Bugs

Forgetting to initialize freq[0] = 1 causes missing counts for subarrays starting at index 0.

2

Iterate Through nums to Accumulate Result Using Prefix Sums

To traverse the array, update prefix sums, and count subarrays summing to goal using the frequency map.

3

Return the Total Count of Valid Subarrays

To output the final count of subarrays whose sum equals the goal.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 10 Critical

res += freq.get(prefix - goal, 0)

Add to result the count of prefix sums equal to prefix - goal.

This line is the core of the algorithm: it counts how many previous prefix sums differ from the current prefix sum by exactly goal, indicating subarrays summing to goal ending at the current index.

Line 5 Critical

freq = {0: 1}

Initialize frequency map with prefix sum zero occurring once.

This initialization accounts for subarrays starting at index zero that sum exactly to the goal, enabling correct counting without special cases.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does checking freq[prefixSum - goal] at each step correctly count the number of subarrays summing to goal?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Binary Subarrays With Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Binary Subarrays With Sum drill

or drill a free problem

1	`class Solution:`
2	`def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:`
3
4	`prefix = 0`
5	`freq = {0: 1}`
6	`res = 0`
7
8	`for num in nums:`
9	`prefix += num`
10	`res += freq.get(prefix - goal, 0)`
11	`freq[prefix] = freq.get(prefix, 0) + 1`
12
13	`return res`