Given a binary array nums and an integer goal, return the number of non-empty subarrays with a sum goal.
A subarray is a contiguous part of the array.
Example 1:
Input: nums = [1,0,1,0,1], goal = 2 Output: 4 Explanation: The 4 subarrays are bolded and underlined below: [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1] [1,0,1,0,1]
Example 2:
Input: nums = [0,0,0,0,0], goal = 0 Output: 15
Constraints:
1 <= nums.length <= 3 * 104nums[i] is either 0 or 1.0 <= goal <= nums.lengthThe key observation in Binary Subarrays With Sum is that the array contains only 0s and 1s. This property enables efficient counting techniques rather than brute-force enumeration of all subarrays.
A common strategy is using a prefix sum with a hash map. As you iterate through the array, maintain a running sum and track how often each prefix sum appears. If the current sum minus the target exists in the map, those previous occurrences represent valid subarrays ending at the current index.
Another optimized method uses a sliding window approach based on counting subarrays with sum atMost(k). By computing the difference between subarrays with sum atMost(goal) and atMost(goal - 1), you can derive the exact number of subarrays that equal the target.
Both techniques avoid the naive O(n^2) enumeration and efficiently process the array in linear time.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum + Hash Map | O(n) | O(n) |
| Sliding Window (atMost technique) | O(n) | O(1) |
Ashish Pratap Singh
The prefix sum approach maintains a running sum and stores it in a hash map to efficiently count subarrays with a given sum. By keeping track of the number of times a particular sum has occurred, this method can determine how many subarrays sum to the desired goal by examining previous prefix sums. This solution is highly efficient as it leverages a linear pass through the array.
Time Complexity: O(N) where N is the length of the array.
Space Complexity: O(N) for storing prefix sums.
1def numSubarraysWithSum(nums, goal):
2 prefix_sum = {0: 1}
3 curr_sum = 0
4 count = 0
5 for num in nums:
6 curr_sum += num
7 count += prefix_sum.get(curr_sum - goal, 0)
8 prefix_sum[curr_sum] = prefix_sum.get(curr_sum, 0) + 1
9 return countThis solution uses a hash map to store prefix sums. As the array is traversed, the current sum is updated. For each element, it checks if curr_sum - goal exists in the hash map, which indicates a valid subarray sum, and updates the count accordingly.
The sliding window technique incrementally builds a window of elements and checks if its sum matches the goal. Upon reaching or exceeding the goal sum, the window is adjusted by moving the left boundary to find more subarrays that might sum to the goal. This approach is useful for fixed-sum searches without repetitive recalculations.
Time Complexity: O(N) where N is the length of the array.
Space Complexity: O(1) because no additional data structures are used.
1public int numSubarraysWithSum(int[] nums, int goalWatch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in FAANG-style interviews. It tests understanding of prefix sums, sliding window techniques, and efficient counting of subarrays.
A hash map is commonly used with the prefix sum approach to store the frequency of previously seen sums. This allows quick lookup of how many earlier prefixes can form the required target sum with the current prefix.
The optimal approaches are prefix sum with a hash map or a sliding window technique using the atMost trick. Both methods process the array in linear time and efficiently count valid subarrays without checking every possible range.
Yes, since the array is binary, a sliding window approach can be applied. By counting subarrays with sum at most a given value and subtracting counts, you can determine the exact number of subarrays with the desired sum.
This Java implementation uses two pointers to define a sliding window. It increments the end pointer to expand the window until the sum exceeds the goal, then adjusts by incrementing start. It checks for additional valid subarrays by traversing zeros past start.