930. Binary Subarrays With Sum

930

MediumPrefix Sum and Difference ArrayHash map of prefix-sum frequenciesPrefix sum counts with hash map

Binary Subarrays With Sum

Given a binary array nums (each element 0 or 1) and an integer goal, return the number of non-empty subarrays whose elements sum to exactly goal. Subarrays are contiguous and different index ranges count separately even if their contents match.

Open official problem prompt ↗

In plain English

Count how many contiguous stretches of the binary array add up to exactly goal.

Picture it like this

Reading a ledger of running balances: to count every span that changed the balance by exactly goal, at each new balance you ask how many past balances were exactly goal lower.

Example

Input: nums = [1, 0, 1, 0, 1], goal = 2
Output: 4
Why: Four index ranges sum to 2: (0-2), (0-3), (1-4) and (2-4)

Constraints

1 <= nums.length <= 3 * 10^4nums[i] is 0 or 10 <= goal <= nums.length

Pattern lesson

See the pattern, then code

Prefix sum counts with hash map

↗

Prefix Sum and Difference Array

Repeated range queries, subarray totals, balanced counts, or batched range updates.. A subarray sums to goal exactly when prefix[j] - prefix[i] = goal. Scanning left to right, for the current prefix sum s, the number of valid starts is how many earlier prefixes equaled s - goal.

New words, made simpleKnow these before the algorithm

Prefix sum frequency: A map recording how many times each running total has occurred so far.
Complement: total - goal, the earlier prefix value that would close a subarray summing to goal.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Enumerate all subarrays

Quadratic on 3*10^4 elements is too slow.

Compute the sum of every start/end pair and count those equal to goal.

Time O(n^2)Space O(1)

Best choicePrefix-sum frequency map

One pass counts all subarrays, including handling goal = 0 cleanly.

For each prefix sum, add how many earlier prefixes equal total - goal.

Time O(n)Space O(n)

The rule we keep true

Invariant

count holds the number of prefixes (including the empty prefix) seen strictly before the current index, keyed by their sum.

Why this is correct

Reasoning

Every subarray ending at the current index with sum goal corresponds to exactly one earlier prefix equal to total - goal. Summing those counts over all endpoints counts every qualifying subarray once. The {0:1} seed accounts for subarrays that start at index 0.

The algorithm in three movesSay these aloud before coding

1Keep a frequency map of prefix sums seen so far, seeded with {0: 1}

count={0:1}

2Maintain the running prefix sum total

s=1 ans+=cnt[-1]=0

3Add count[total - goal] to the answer at each step

s=2 ans+=cnt[0]=1

4Increment count[total] and continue

s=2 ans+=cnt[0]=2

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readbefore loop

2 · AskBaseline prefix?

3 · Update statecount={0:1}, total=0, ans=0

4 · ResultEmpty prefix recorded

Key takeaway

Running prefix sums; each step adds how many earlier prefixes equal total - goal.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Initialize state
count seeded with the empty prefix; total and ans start at zero.
2
Lines 7-9Count then record
Add matches for the current endpoint first, then register the current prefix so a subarray cannot use itself as its own start.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

goal = 0 counts subarrays of only zeros, handled because total - 0 = total matches repeats
An all-ones array with goal equal to its length yields exactly one subarray
Single-element arrays return 1 when that element equals goal

Common beginner mistakes

Recording count[total] before adding to the answer, which would count zero-length subarrays for goal 0
Forgetting the {0:1} seed, undercounting subarrays that begin at index 0
Assuming values can exceed 1; this specific problem is binary, but the map approach still generalizes

Check your understanding

Why must we update the answer before incrementing count[total]?

Binary Subarrays With Sum

Binary Subarrays With Sum

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Prefix Sum and Difference Array