# Leetcode 930 - Binary Subarrays With Sum

### Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.

### 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

**is the sum of the first**

`prefix[i]`

**elements of**

`i`

**.**

`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

**and have a sum of**

`i`

**by looking at the number of subarrays that start at**

`s`

**and end at**

`j`

**and have a sum of**

`i-1`

**. We can do this by keeping track of the frequency of each sum in a dictionary.**

`s - arr[i]`

We can initialize the dictionary with a key ** 0** and a value of

**. This is because there is always one subarray with a sum of 0, which is the empty subarray.**

`1`

For each ** i**, we increment the frequency of the sum

**in the dictionary and add the frequency to the count of subarrays that end at**

`s - arr[i]`

**and have a sum of**

`i`

**.**

`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

**using a prefix sum array and a dictionary.**

`s`

### Advance your Tech Career to new heights with Personalized Coaching from industry Experts at top companies.

**Related:**