Binary Subarrays With Sum

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

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.