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

Brute Force With Space

Java Code

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        Map<Integer, Integer> sumFrequencyMap = new HashMap<>();
        int prefixSum = 0;
        int count = 0;

        for(int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];

            if(prefixSum == goal) {
                count += 1;
            }
            
            if(sumFrequencyMap.containsKey(prefixSum - goal)) {
                count += sumFrequencyMap.get(prefixSum - goal);
            }

            sumFrequencyMap.put(prefixSum, sumFrequencyMap.getOrDefault(prefixSum, 0) + 1);
        }

        return count;
    }
}

C++ Code

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        unordered_map<int, int> sumFrequencyMap;
        int prefixSum = 0;
        int count = 0;

        for (int num : nums) {
            prefixSum += num;

            if (prefixSum == goal) {
                count += 1;
            }

            if (sumFrequencyMap.find(prefixSum - goal) != sumFrequencyMap.end()) {
                count += sumFrequencyMap[prefixSum - goal];
            }

            sumFrequencyMap[prefixSum]++;
        }

        return count;
    }
};

Python Code

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        sumFrequencyMap = {}
        prefixSum = 0
        count = 0

        for num in nums:
            prefixSum += num

            if prefixSum == goal:
                count += 1

            if prefixSum - goal in sumFrequencyMap:
                count += sumFrequencyMap[prefixSum - goal]

            sumFrequencyMap[prefixSum] = sumFrequencyMap.get(prefixSum, 0) + 1

        return count

Javascript Code

/**
 * @param {number[]} nums
 * @param {number} goal
 * @return {number}
 */
var numSubarraysWithSum = function(nums, goal) {
    const sumFrequencyMap = new Map();
    let prefixSum = 0;
    let count = 0;

    for (const num of nums) {
        prefixSum += num;

        if (prefixSum === goal) {
            count += 1;
        }

        if (sumFrequencyMap.has(prefixSum - goal)) {
            count += sumFrequencyMap.get(prefixSum - goal);
        }

        sumFrequencyMap.set(
            prefixSum,
            (sumFrequencyMap.get(prefixSum) || 0) + 1
        );
    }

    return count;
};

Optimised Without Space

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.