Binary Subarrays With Sum

Problem Description

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

Key Insights

• A subarray is defined as a contiguous segment of the array.
• The sum of the elements in a binary array can only be 0 or 1, simplifying the problem.
• We can use prefix sums to efficiently count the number of subarrays that sum up to goal.
• A hash map can be utilized to track the frequency of prefix sums encountered so far.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input array nums.
Space Complexity: O(n), due to the storage of prefix sums in a hash map.

Solution

We will use a prefix sum approach with a hash map to keep track of the cumulative sums and their frequencies. The algorithm works as follows:

1. Initialize a hash map to store the frequency of prefix sums, starting with the prefix sum of 0 initialized to 1.
2. Iterate through the array while maintaining a cumulative sum.
3. For each element, calculate the current cumulative sum and check if the difference between the cumulative sum and the goal exists in the hash map. If it does, it means we have found a valid subarray.
4. Update the hash map with the current cumulative sum.

This approach efficiently counts the number of valid subarrays in a single pass through the array.

Code Solutions