Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumprefix-sum

Binary Subarrays With Sum

Problem (restated)

Given a binary array and goal, return the number of non-empty subarrays with sum == goal.

Intuition

Classic prefix-count: for each prefix S, add count of prefixes equal to S-goal.

Approaches

Prefix sum hash

Unverified

Time O(n)Space O(n)

Idea. Map prefix→count; initialize prefix 0 with count 1; accumulate answers.

Walkthrough. [1,0,1,0,1], goal=2 → 4 subarrays.

Trade-offs. Sliding window atMost(goal)-atMost(goal-1) also works for binary arrays.

Solution

export function numSubarraysWithSum(nums: number[], goal: number): number {
  const map = new Map<number, number>([[0, 1]]);
  let sum = 0, ans = 0;
  for (const x of nums) {
    sum += x;
    ans += map.get(sum - goal) ?? 0;
    map.set(sum, (map.get(sum) ?? 0) + 1);
  }
  return ans;
}

export function numSubarraysWithSum(nums: number[], goal: number): number {
  const map = new Map<number, number>([[0, 1]]);
  let sum = 0, ans = 0;
  for (const x of nums) {
    sum += x;
    ans += map.get(sum - goal) ?? 0;
    map.set(sum, (map.get(sum) ?? 0) + 1);
  }
  return ans;
}

Template connection

Prefix-sum hash (or atMost(goal) − atMost(goal-1)) for binary subarrays.

Reflection

Count prefixes. How many earlier prefixes equal pref - goal? Seed prefix 0 with count 1.
On a binary array, atMost(goal) - atMost(goal - 1) is the other O(n) form. Why is that window O(1) memory while the hash is not?
goal = 0 counts only the runs of zeros.