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

Related Posts

• Leetcode 424 - Longest Repeating Character Replacement
• Two Sum and Its Variants
• Leetcode 1004 - Max Consecutive Ones III
• Leetcode 1027 - Longest Arithmetic Subsequence
• Question 1299 on leetcode
• Leetcode 240 - Search a 2D Matrix II
• Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
• Leetcode 239 - Sliding Window Maximum
• Leetcode 209 - Minimum Size Subarray Sum
• LeetCode 230 - Kth Smallest Element in a BST with Code
• advanced-applications-of-binary-search
• Leetcode 96 - Unique Binary Search Trees
• Leetcode 540 - Single Element in a Sorted Array
• Leetcode 1283 - Find the Smallest Divisor Given a Threshold
• Leetcode 74 - Search a 2D Matrix
• Leetcode 300 - Longest Increasing Subsequence
• Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
• Leetcode 704 - Binary Search
• Leetcode 643 - Maximum Average Subarray I
• LeetCode - Two Sum Solution with Code
• a-binary-search-template
• Leetcode 1358 - Number of Substrings Containing All Three Characters
• Leetcode 33 - Search in Rotated Sorted Array
• Leetcode 1151 - Minimum Swaps to Group All 1’s Together