Binary Subarrays With Sum
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
nums = [1,0,1,0,1], goal = 24The 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
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. Iterating once through the array, updating prefix sums and frequencies, yields an O(n) solution.
Optimal Approach
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.
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.
Pattern Spotlight
Prefix Sum (Frequency Counting)
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.
Solution
| 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 |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int numSubarraysWithSum(int[] nums, int goal) { |
| 6 | int prefix = 0; |
| 7 | Map<Integer, Integer> freq = new HashMap<>(); |
| 8 | freq.put(0, 1); |
| 9 | int res = 0; |
| 10 | |
| 11 | for (int num : nums) { |
| 12 | prefix += num; |
| 13 | res += freq.getOrDefault(prefix - goal, 0); |
| 14 | freq.put(prefix, freq.getOrDefault(prefix, 0) + 1); |
| 15 | } |
| 16 | |
| 17 | return res; |
| 18 | } |
| 19 | } |
| 1 | #include <vector> |
| 2 | #include <unordered_map> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | int numSubarraysWithSum(vector<int>& nums, int goal) { |
| 9 | int prefix = 0; |
| 10 | unordered_map<int, int> freq; |
| 11 | freq[0] = 1; |
| 12 | int res = 0; |
| 13 | |
| 14 | for (int num : nums) { |
| 15 | prefix += num; |
| 16 | res += freq[prefix - goal]; |
| 17 | freq[prefix]++; |
| 18 | } |
| 19 | |
| 20 | return res; |
| 21 | } |
| 22 | }; |
| 1 | var numSubarraysWithSum = function(nums, goal) { |
| 2 | let prefix = 0; |
| 3 | const freq = new Map(); |
| 4 | freq.set(0, 1); |
| 5 | let res = 0; |
| 6 | |
| 7 | for (const num of nums) { |
| 8 | prefix += num; |
| 9 | res += freq.get(prefix - goal) || 0; |
| 10 | freq.set(prefix, (freq.get(prefix) || 0) + 1); |
| 11 | } |
| 12 | |
| 13 | return res; |
| 14 | }; |
Step-by-Step Solution
Initialize Prefix Sum and Frequency Map
| 4 | prefix = 0 |
| 5 | freq = {0: 1} |
| 6 | res = 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.
Iterate Through nums to Accumulate Result Using Prefix Sums
| 8 | for num in nums: |
| 9 | prefix += num |
| 10 | res += freq.get(prefix - goal, 0) |
| 11 | freq[prefix] = freq.get(prefix, 0) + 1 |
Objective
To traverse the array, update prefix sums, and count subarrays summing to goal using the frequency map.
Key Insight
At each element, the prefix sum is updated by adding the current number. The algorithm then checks how many prefix sums equal prefixSum - goal have been seen, adding that count to the result. Finally, it updates the frequency map with the current prefix sum. This approach counts all valid subarrays ending at the current index in O(1) time per element.
Interview Quick-Check
Core Logic
The key step is adding freq.get(prefix - goal, 0) to the result, which counts all subarrays ending at the current index with sum equal to goal.
State & Boundaries
The prefix sum and frequency map are updated in each iteration to reflect the current state of the traversal.
Common Pitfalls & Bugs
Updating freq[prefix] after counting ensures the current prefix sum is available for future subarray calculations without double counting.
Return the Total Count of Valid Subarrays
| 13 | return res |
Objective
To output the final count of subarrays whose sum equals the goal.
Key Insight
After processing all elements, the accumulated result holds the total number of valid subarrays. Returning it completes the algorithm.
Interview Quick-Check
Core Logic
Returning res after the loop provides the total count of subarrays summing to goal.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
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.
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.
freq[prefix] = freq.get(prefix, 0) + 1Increment the frequency count for the current prefix sum.
Updating the frequency map after counting ensures the current prefix sum is available for future subarray calculations without double counting or missing subarrays.
prefix += numUpdate prefix sum by adding the current number.
Maintaining a running prefix sum allows the algorithm to compute subarray sums as differences between prefix sums efficiently.
return resReturn the total count of subarrays summing to goal.
After processing all elements, the accumulated result represents the total number of valid subarrays, completing the solution.
prefix = 0Initialize prefix sum accumulator to zero.
Starting prefix sum at zero represents the sum of an empty prefix, which is the baseline for all subsequent prefix sums.
for num in nums:Iterate through each number in the input array.
Sequential traversal is necessary to build prefix sums and count valid subarrays ending at each index.
res = 0Initialize result accumulator to zero.
This variable will accumulate the total count of valid subarrays found during iteration.
Test Your Understanding
Why does checking freq[prefixSum - goal] at each step correctly count the number of subarrays summing to goal?
Because the difference between the current prefix sum and a previous prefix sum equals the sum of the subarray between those indices; thus, freq[prefixSum - goal] counts how many subarrays ending at the current index sum to goal.
Related Problems
Prefix Sum pattern
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