Binary Subarrays With Sum

Practice Link

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.

Prefixsum + Hashmap#

Maintain a running prefix sum and count how many previous prefix sums equal currentSum - goal. If such a prefix sum exists, the subarray between that earlier index and the current index has exactly the required sum. Storing prefix sum frequencies in a hash map lets each lookup happen in O(1), resulting in an O(n) overall pass. The trade-off is O(n) extra space for the map.

class Solution {
public:

    int numSubarraysWithSum(vector<int>& nums, int goal) {
        unordered_map<int,int> prefixCount;
        prefixCount[0]=1;
        int sum=0,cnt=0;

        for(int i=0;i<nums.size();i++)
        {
            sum += nums[i];
            if(prefixCount.count(sum-goal))
                cnt += prefixCount[sum-goal];
            prefixCount[sum]++;
        }
        return cnt;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Sliding window Approach#

A direct sliding window for an exact sum is tricky because shrinking from the left stops as soon as the sum drops below the goal, making it hard to count exact matches. The trick is to reframe: count(subarrays with sum == goal) = count(subarrays with sum \<= goal) − count(subarrays with sum \<= goal-1). The helper function counts subarrays with sum at most goal using a standard shrinkable window, and the difference gives the exact count. This achieves O(n) time with O(1) extra space.

class Solution {
public:
    int helper(vector<int> &nums, int goal)
    {
        if(goal<0)
            return 0;
        int l = 0,r=0;

        int currSum = 0, cnt=0;
        while(r < nums.size())
        {
            currSum += nums[r];
            while(currSum > goal && l<=r)
            {
                currSum -= nums[l];
                l++;
            }
            cnt += (r-l+1);
            r++;
        }
        return cnt;
    }
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        return helper(nums, goal)-helper(nums, goal-1);
    }
};

Time Complexity: O(n)

Space Complexity: O(1)