Binary Subarray with Sum

Count subarrays of 0/1 numbers whose sum equals a given goal using an efficient sliding window.

sliding-window two-pointers subarray

Implement the function `num_subarrays_with_sum(nums, goal)` that takes a list `nums` containing only 0s and 1s, and an integer `goal`, and returns the number of non-empty contiguous subarrays whose sum equals `goal`. The solution must run in O(n) time using O(1) extra space (not counting the input).

Constraints

1 <= len(nums) <= 10^5
0 <= goal <= len(nums)
Each element of nums is either 0 or 1.
The answer fits in a 64-bit integer.

Example

>>> num_subarrays_with_sum([1,0,1,0,1], 2)
4
>>> num_subarrays_with_sum([0,0,0,0,0], 0)
15

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Try to write a helper that counts subarrays with sum at most a given target.

For a subarray with sum at most x, use a sliding window that expands right and shrinks left when the sum exceeds x.

The answer is at_most(goal) - at_most(goal-1) (for goal > 0); handle goal=0 separately or adjust the helper to return 0 for negative targets.

What is the count of subarrays ending at each right index while the window is valid?

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.