Leetcode 930 - Binary Subarrays With Sum

Understanding the problem

You are given an array of binary integers arr and an integer s.

Return the number of non-empty subarrays of arr that have a sum equal to s.

A subarray is a contiguous subsequence of the array.

Example:

Input: arr = [1,0,1,0,1], s = 2

Output: 4

Explanation: There are 4 subarrays with a sum of 2:

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

[1,0,1,0,1]

Input: arr = [0,0,0,0,0], s = 0

Output: 15

Explanation: There are 15 subarrays with a sum of 0:

[0]

[0]

[0]

[0]

[0]

[0,0]

[0,0]

[0,0]

[0,0]

[0,0]

[0,0,0]

[0,0,0]

[0,0,0]

[0,0,0]

[0,0,0,0]

Constraints:

• 1 <= arr.length <= 10^5
• 0 <= s <= arr.length

Plan your solution

One approach to solve this problem is to use a prefix sum array.

We can start by initializing a prefix sum array prefix where prefix[i] is the sum of the first i elements of arr.

Then, we can iterate over the elements of arr and use the prefix sum array to count the number of subarrays with a sum of s.

For each i, we can find the number of subarrays that end at i and have a sum of s by looking at the number of subarrays that start at j and end at i-1 and have a sum of s - arr[i]. We can do this by keeping track of the frequency of each sum in a dictionary.

We can initialize the dictionary with a key 0 and a value of 1. This is because there is always one subarray with a sum of 0, which is the empty subarray.

For each i, we increment the frequency of the sum s - arr[i] in the dictionary and add the frequency to the count of subarrays that end at i and have a sum of s.

Finally, we return the count of subarrays.

Implement your solution

Now let’s implement the solution in Python.

class Solution:
    def numSubarraysWithSum(self, arr: List[int], s: int) -> int:
        # Initialize prefix sum array
        prefix = [0] * (len(arr) + 1)
        for i in range(len(arr)):
            prefix[i+1] = prefix[i] + arr[i]
        
        # Initialize dictionary with a key 0 and a value of 1
        d = {0: 1}
        count = 0
        # Iterate over elements of arr
        for i in range(len(arr)):
            # Increment the frequency of the sum s - arr[i] in the dictionary
            # Add the frequency to the count of subarrays that end at i and have a sum of s
            count += d.get(prefix[i+1] - s, 0)
            d[prefix[i+1]] = d.get(prefix[i+1], 0) + 1
        
        # Return count
        return count

Test your solution

Now we can test our solution with some test cases.

arr = [1,0,1,0,1]
s = 2
assert numSubarraysWithSum(arr, s) == 4

arr = [0,0,0,0,0]
s = 0
assert numSubarraysWithSum(arr, s) == 15

arr = [1,1,1,1,1]
s = 1
assert numSubarraysWithSum(arr, s) == 15

arr = [0,1,1,1,1]
s = 2
assert numSubarraysWithSum(arr, s) == 7

arr = [1,1,1,1,0]
s = 2
assert numSubarraysWithSum(arr, s) == 8

All the test cases pass, which means our solution is correct.

That’s it! We have successfully implemented a solution to find the number of non-empty subarrays of arr that have a sum equal to s using a prefix sum array and a dictionary.

Related:

• single element in a sorted array
• search in rotated sorted array
• binary search
• unique binary search trees