Binary Subarrays With Sum - LeetCode Daily Challenge

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

Try here before watching the video.

Video Explanation

Java Code

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int start = 0, count = 0, prefixZeros = 0, sum = 0;

        for(int end = 0; end < nums.length; end++) {
            sum += nums[end];
            while(start < end && (nums[start] == 0 || sum > goal)) {
                if(nums[start] == 0) {
                    prefixZeros += 1;
                } else {
                    prefixZeros = 0;
                }
                sum -= nums[start];
                start += 1;
            }

            if(sum == goal) {
                count += (1 + prefixZeros);
            }
        }

        return count;
    }
}

C++ Code

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int start = 0, count = 0, prefixZeros = 0, sum = 0;

        for(int end = 0; end < nums.size(); end++) {
            sum += nums[end];
            while(start < end && (nums[start] == 0 || sum > goal)) {
                if(nums[start] == 0) {
                    prefixZeros += 1;
                } else {
                    prefixZeros = 0;
                }
                sum -= nums[start];
                start += 1;
            }

            if(sum == goal) {
                count += (1 + prefixZeros);
            }
        }

        return count;
    }
};

Python Code

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        start = 0
        count = 0
        prefixZeros = 0
        sum_val = 0

        for end in range(len(nums)):
            sum_val += nums[end]
            while start < end and (nums[start] == 0 or sum_val > goal):
                if nums[start] == 0:
                    prefixZeros += 1
                else:
                    prefixZeros = 0
                sum_val -= nums[start]
                start += 1

            if sum_val == goal:
                count += (1 + prefixZeros)

        return count

Javascript Code

var numSubarraysWithSum = function(nums, goal) {
    let start = 0, count = 0, prefixZeros = 0, sum = 0;

    for(let end = 0; end < nums.length; end++) {
        sum += nums[end];
        while(start < end && (nums[start] === 0 || sum > goal)) {
            if(nums[start] === 0) {
                prefixZeros += 1;
            } else {
                prefixZeros = 0;
            }
            sum -= nums[start];
            start += 1;
        }

        if(sum === goal) {
            count += (1 + prefixZeros);
        }
    }

    return count;
};

Go Code

func numSubarraysWithSum(nums []int, goal int) int {
    start := 0
    count := 0
    prefixZeros := 0
    sum := 0

    for end := 0; end < len(nums); end++ {
        sum += nums[end]
        for start < end && (nums[start] == 0 || sum > goal) {
            if nums[start] == 0 {
                prefixZeros++
            } else {
                prefixZeros = 0
            }
            sum -= nums[start]
            start++
        }

        if sum == goal {
            count += (1 + prefixZeros)
        }
    }

    return count
}

Complexity Analysis

Time Complexity: O(N), where N is the number of elements in array nums. This is because we are iterating the entire array only once.
Space Complexity: O(1), we are not taking any extra space.