930. Binary Subarrays With Sum LeetCode Solution

In this guide, you will get 930. Binary Subarrays With Sum LeetCode Solution with the best time and space complexity. The solution to Binary Subarrays With Sum problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Binary Subarrays With Sum solution in C++
Binary Subarrays With Sum solution in Java
Binary Subarrays With Sum solution in Python
Additional Resources

930. Binary Subarrays With Sum LeetCode Solution image

Problem Statement of Binary Subarrays With Sum

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 * 104
nums[i] is either 0 or 1.
0 <= goal <= nums.length

Complexity Analysis

Time Complexity:
Space Complexity:

930. Binary Subarrays With Sum LeetCode Solution in C++

class Solution {
 public:
  int numSubarraysWithSum(vector<int>& nums, int goal) {
    int ans = 0;
    int prefix = 0;
    // {prefix: number of occurrence}
    unordered_map<int, int> count{{0, 1}};

    for (const int num : nums) {
      prefix += num;
      if (const auto it = count.find(prefix - goal); it != count.cend())
        ans += it->second;
      ++count[prefix];
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

930. Binary Subarrays With Sum LeetCode Solution in Java

class Solution {
  public int numSubarraysWithSum(int[] nums, int goal) {
    int ans = 0;
    int prefix = 0;
    // {prefix: number of occurrence}
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);

    for (final int num : nums) {
      prefix += num;
      final int key = prefix - goal;
      if (count.containsKey(key))
        ans += count.get(key);
      count.merge(prefix, 1, Integer::sum);
    }

    return ans;
  }
}
// code provided by PROGIEZ

930. Binary Subarrays With Sum LeetCode Solution in Python

class Solution:
  def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
    ans = 0
    prefix = 0
    # {prefix: number of occurrence}
    count = collections.Counter({0: 1})

    for num in nums:
      prefix += num
      ans += count[prefix - goal]
      count[prefix] += 1

    return ans
 # code by PROGIEZ