Binary Subarrays With Sum - Leetcode Solution

Problem Statement:

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:

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}]

Approach: We can use the sliding window technique to solve this problem. We can keep track of the sum of the elements in the current window using two pointers - l and r. We initialize both l and r pointers to 0 and move r to the right. If the sum of the elements in the current window is less than the given goal, we move r pointer to the right and add the element to the current sum. If the sum of the elements in the current window is greater than the given goal, we move l pointer to the right and subtract the element from the current sum. If the sum of the elements in the current window is equal to the given goal, we increment the count of subarrays by 1 and move l pointer to the right and subtract the element from the current sum.

Algorithm:

1. Initialize l pointer, r pointer, current sum and count of subarrays to 0.
2. Traverse the given binary array nums from left to right while moving the r pointer to the right.
3. Add the current element to the current sum.
4. If the sum of the elements in the current window is greater than the given goal, then move the l pointer to the right and subtract the element from the current sum until the sum is less than or equal to the given goal.
5. If the sum of the elements in the current window is equal to the given goal, increment the count of subarrays by 1 and move l pointer to the right and subtract the element from the current sum.
6. Return the count of subarrays.

Python Code:

class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: l, r, curr_sum, count = 0, 0, 0, 0 n = len(nums) while r < n: curr_sum += nums[r] while l <= r and curr_sum > goal: curr_sum -= nums[l] l += 1 if curr_sum == goal: count += 1 i = l while i < r and nums[i] == 0: count += 1 i += 1 r += 1 return count

Time Complexity: O(n) Space Complexity: O(1)

Explanation:

1. We define four variables namely l, r, current sum and count of subarrays with sum goal. We then set them to 0 and calculate the length of the given binary array in variable n.
2. We loop through the array with the r pointer moving towards the right.
3. We add the current element to the current sum.
4. If the sum of the elements in the current window is greater than the given goal, we move the l pointer to the right and subtract the element from the current sum until the sum is less than or equal to the given goal.
5. If the sum of the elements in the current window is equal to the given goal, we increment the count of subarrays by 1 and check for possible combinations of zeros between two ones in the subarray resulting in the sum. If there are more than one zero between two ones, we increment the count of subarrays accordingly.
6. We continue the process until the entire array is traversed and return the count of subarrays.

1