Binary Subarrays With Sum

How it works

Counting subarrays with exactly goal sum is tricky with a sliding window because shrinking the window might skip valid subarrays. However, counting subarrays with sum at most goal is straightforward. We can use the identity: count(exactly goal) = count(at most goal) - count(at most goal-1). For each right endpoint, we shrink the left side until the sum is at most the target, and all subarrays ending at right with starting points from left to right are valid.

Steps

1. Define a helper function that counts subarrays with sum at most x.
2. In the helper, use two pointers (left and right) with a running sum.
3. For each right, add nums[right] to the sum. While sum > x, shrink from the left.
4. Add (right - left + 1) to the count, representing all valid subarrays ending at right.
5. Return helper(goal) - helper(goal - 1) as the final answer.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Forgetting to Initialize Prefix Sum Count with Zero

The hash map must start with {0: 1} to count subarrays that start from index 0. Without this, subarrays where the prefix sum exactly equals the goal are missed.

Not Handling goal = 0 in Sliding Window

When using the sliding window approach, helper(goal - 1) becomes helper(-1). Without the early return for negative values, the window logic breaks and may produce incorrect results or infinite loops.

Breaking Early When Sum Exceeds Goal

In the brute force approach, some incorrectly add a break when curSum > goal. This is wrong because the array contains only 0s and 1s, and adding more 0s keeps the sum unchanged, potentially finding more valid subarrays.

from typing import List

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        def helper(x):
            if x < 0:
                return 0
            res = l = cur = 0
            for r in range(len(nums)):
                cur += nums[r]
                while cur > x:
                    cur -= nums[l]
                    l += 1
                res += (r - l + 1)
            return res

        return helper(goal) - helper(goal - 1)

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        return helper(nums, goal) - helper(nums, goal - 1);
    }

private:
    int helper(vector<int>& nums, int x) {
        if (x < 0) return 0;
        int res = 0, l = 0, cur = 0;
        for (int r = 0; r < nums.size(); r++) {
            cur += nums[r];
            while (cur > x) {
                cur -= nums[l];
                l++;
            }
            res += (r - l + 1);
        }
        return res;
    }
};