Binary Subarrays With Sum [Medium] — Prefix Sum / atMost

Problem Statement

Given a binary array nums and integer goal, return the number of non-empty subarrays with a sum equal to goal.

Input: nums=[1,0,1,0,1], goal=2 → Output: 4

Intuition

Prefix Sum: Count prefix sums. For each prefix P[i], check how many previous prefixes equal P[i]-goal.

Alternative: exactly(goal) = atMost(goal) - atMost(goal-1).

Solutions

C++

int numSubarraysWithSum(vector<int>& nums, int goal) {
    unordered_map<int,int> cnt; cnt[0]=1;
    int prefix=0, ans=0;
    for(int n:nums){prefix+=n;ans+=cnt[prefix-goal];cnt[prefix]++;}
    return ans;
}

Java

public int numSubarraysWithSum(int[] nums, int goal) {
    Map<Integer,Integer> cnt=new HashMap<>(); cnt.put(0,1);
    int prefix=0, ans=0;
    for(int n:nums){prefix+=n;ans+=cnt.getOrDefault(prefix-goal,0);cnt.merge(prefix,1,Integer::sum);}
    return ans;
}

Python

from collections import defaultdict

def numSubarraysWithSum(nums: list[int], goal: int) -> int:
    cnt = defaultdict(int)
    cnt[0] = 1
    prefix = ans = 0
    for n in nums:
        prefix += n
        ans += cnt[prefix - goal]
        cnt[prefix] += 1
    return ans

Complexity

Time: O(n), Space: O(n)