Problem Description
Given a binary array and an integer goal, count the number of non-empty contiguous subarrays (subarrays) whose elements sum to goal.
Key Insights
- Instead of evaluating every subarray (which would be inefficient), use a prefix sum technique.
- Maintain a hash map (or dictionary) to count how many times a certain prefix sum appears.
- For each new prefix sum (running sum), check if there is a previous prefix sum equal to (current prefix sum - goal). If yes, the difference gives a valid subarray.
- The approach efficiently handles both positive and zero values especially given the array contains only 0s and 1s.
Space and Time Complexity
Time Complexity: O(n) where n is the length of the array. Space Complexity: O(n) in the worst case for storing prefix sums in the hash map.
Solution
We use the prefix sum method along with a hash table to map the cumulative sum to its frequency. Start with an initial prefix sum of 0 with a frequency of 1. As you loop through the array, update the cumulative sum. Check if (cumulative sum - goal) exists in the hash table; if it does, add its frequency to the result counter because it means there are one or more subarrays ending at the current index with the desired sum. Finally, update the hash table with the new cumulative sum. This method efficiently computes the desired count in a single pass over the array.