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 sum equals goal.

A subarray is a contiguous part of the array.

Hints

· Stuck? Reveal one nudge at a time.

Counting exactly-goal directly is awkward — is there an easier quantity to count?

count(exactly goal) = count(at most goal) - count(at most goal - 1).

Write a sliding-window atMost(k) that adds right-left+1 per step, and call it twice.

Common doubts

atMost(goal) counts every subarray with sum <= goal; subtracting those with sum <= goal-1 removes all but the ones with sum exactly goal.

Once the window [left, right] has sum <= k, every subarray ending at right and starting anywhere in [left, right] also has sum <= k — that's right - left + 1 subarrays.

atMost(-1) must return 0. Then the answer is atMost(0) - 0 = the number of all-zero subarrays, which is correct.

Interview follow-ups

· What an interviewer asks next.

Count how many earlier prefix sums equal current_prefix - goal; that's an alternate O(n) approach that also works for non-binary arrays.

It needs non-negative values so the window sum is monotone as you extend/shrink; binary is a special case. Negative values break the monotonicity.

Fun facts

The atMost(k) - atMost(k-1) identity is the single most reused trick for 'exactly k' subarray-counting problems.
The very same code, with 'odd number' playing the role of '1', solves Count Number of Nice Subarrays.

Asked at

AmazonGoogleFacebook

Frequently Sometimes Occasionally

Example 1

Input: nums = [1,0,1,0,1], goal = 2
Output: 4
There are 4 subarrays summing to 2.

Example 2

Input: nums = [0,0,0,0,0], goal = 0
Output: 15
Every one of the 15 non-empty subarrays sums to 0.

Constraints

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

Counting subarrays with sum exactly goal is awkward directly, but there's a clean identity: exactly goal = at most goal − at most (goal − 1). And "at most k" is an easy sliding window, because on a binary array the window sum only grows on a 1 and shrinks as you drop from the left.

Prerequisites

Before you start

· Concepts used directly in the solution.

atMost trick. count(exactly k) = count(at most k) − count(at most k − 1).

Sliding window count. The number of subarrays ending at right with a valid window is right − left + 1.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The count

“Are subarrays counted by position?”

Yes — every contiguous range with the target sum counts, even if identical in content to another.

“Can goal be 0?”

Yes — then you're counting subarrays of all zeros; the identity still works since at most -1 is 0.

The ideal opening — say it like this

Exactly goal is hard to window directly, so I'll use exactly = atMost(goal) minus atMost(goal-1).

atMost(k) is a simple window: grow the right, shrink while the sum exceeds k, and add right-left+1 each step.

Subtracting the two atMost counts leaves exactly the subarrays summing to goal.

Understand the problem

Worked example — nums = [1,0,1,0,1], goal = 2

atMost(2) counts all subarrays with sum <= 2
atMost(1) counts all subarrays with sum <= 1
answer = atMost(2) - atMost(1) = 4

Key observations

1Aha

Exactly k via two at-most counts

count(sum == goal) = atMost(goal) - atMost(goal - 1). This converts an awkward exact-count into two easy monotone-window counts.

2Aha

atMost is a clean window

On each right, subarrays ending there with sum <= k are exactly those starting in [left, right], so add right - left + 1. Shrink from the left whenever the sum passes k.

3Aha

goal - 1 can be negative

When goal is 0, atMost(-1) must be 0 (no subarray has negative sum) — a one-line guard makes the identity hold at the boundary.

Brute force vs optimal

	Sum every subarray	atMost(goal) − atMost(goal−1)
Idea	Accumulate each subarray sum, count == goal	Two sliding-window at-most counts, subtracted
Time	O(n^2)	O(n)
Space	O(1)	O(1)

The brute sums every subarray; the identity replaces it with two linear passes. Full code is in the Approaches selector below.

Summary

Key takeaway

Count subarrays with sum exactly goal as atMost(goal) - atMost(goal - 1). atMost(k) slides a window, adding right - left + 1 at each step and shrinking whenever the sum exceeds k. Two O(n) passes, O(1) space.

def atMost(k):
    if k < 0: return 0
    left = 0; total = 0; sum = 0
    for right in 0 .. n-1:
        sum += nums[right]
        while sum > k: sum -= nums[left]; left += 1
        total += right - left + 1
    return total
return atMost(goal) - atMost(goal - 1)