Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

Problem gist

Given a binary array nums and a nonnegative integer goal, count the nonempty contiguous subarrays whose elements add up to exactly goal.

Contiguous and exact are the important words. The same element may belong to many valid subarrays, and zeros create several subarrays with the same sum. For example, in [1, 0, 1, 0, 1], there are four different subarrays whose sum is 2.

Checking every pair of endpoints would take O(n^2) time. The array’s nonnegative values make a linear-time sliding window possible, but counting only the windows whose current sum equals goal is not enough: leading zeros can create several valid starting positions for one right endpoint. A small reformulation handles all of them cleanly.

Deriving the sliding-window solution

Let at_most(limit) mean the number of subarrays whose sum is at most limit. Every subarray counted by at_most(goal) belongs to exactly one of two groups: its sum is at most goal - 1, or its sum is exactly goal. Therefore,

exactly(goal) = at_most(goal) - at_most(goal - 1)

Counting at_most(limit) is straightforward because every value is nonnegative. Extend a window one element at a time. If its sum exceeds limit, move the left boundary right until the window is valid again. Once the window from left through right is valid, every suffix ending at right is also valid, so there are right - left + 1 valid subarrays ending there.

The key invariant is that, after shrinking, [left, right] is the longest valid window ending at right. Nonnegativity guarantees that removing more elements cannot increase the sum, so all later starting positions are valid. Each array element enters the window once and leaves it at most once, giving O(n) time and O(1) extra space. Returning zero immediately for a negative limit also makes the formula work when goal is zero.

An equally optimal prefix-sum alternative

A prefix sum gives a second O(n) solution. Suppose the running sum at the current position is current_sum. A subarray ending here has sum goal when an earlier prefix sum equals current_sum - goal. A frequency map of earlier prefix sums tells how many such starting points exist.

This method uses O(n) extra space, but it works even if the array contains negative values. The sliding-window method is preferable for this problem because the binary-array guarantee reduces the extra space to O(1).

Python solution

The helper implements the reusable “count at most” operation. The public method subtracts two cumulative counts to isolate the exact target.

from collections.abc import Sequence


class Solution:
    """Count binary subarrays whose sum equals a requested goal."""

    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        """Return the number of nonempty contiguous subarrays summing to goal."""
        return self._count_at_most(nums, goal) - self._count_at_most(
            nums,
            goal - 1,
        )

    @staticmethod
    def _count_at_most(nums: Sequence[int], limit: int) -> int:
        """Count subarrays whose sum is no greater than limit in O(n) time."""
        if limit < 0:
            return 0

        left = 0
        window_sum = 0
        subarray_count = 0

        for right, value in enumerate(nums):
            window_sum += value

            # Restore the invariant that the current window sum is at most limit.
            while window_sum > limit:
                window_sum -= nums[left]
                left += 1

            # Every suffix of nums[left : right + 1] ending at right is valid.
            subarray_count += right - left + 1

        return subarray_count

Interview follow-ups

Why not count the moments when a sliding window’s sum equals goal?

One current window does not represent every valid starting point. If its left side contains zeros, removing any number of those zeros produces another subarray with the same sum and the same right endpoint. A loop that merely expands, shrinks when too large, and adds one when the sum matches would undercount those alternatives.

The at-most transformation counts all valid suffixes at every right endpoint and then removes those with smaller sums. Another correct approach would explicitly count removable leading zeros, but it requires more case handling, especially when goal is zero.

What changes if the array can contain negative numbers?

The sliding-window proof breaks because removing the leftmost value might increase the sum, and extending the right boundary might decrease it. There is no longer a monotonic way to restore an at-most constraint.

Use the prefix-sum frequency map instead. Initialize the map with {0: 1}. For each value, update the running sum, add the stored frequency of running_sum - goal to the answer, and then increment the frequency of running_sum. This remains O(n) time but needs O(n) space.

Can the binary values be exploited without subtracting two at-most counts?

Yes. For a positive goal, record the positions of the ones. Every group of goal consecutive ones determines the mandatory middle of a valid subarray. The number of choices to extend left through adjacent zeros, multiplied by the number of choices to extend right through adjacent zeros, gives that group’s contribution.

For goal = 0, each run of z zeros contributes z * (z + 1) / 2 subarrays. This method is also O(n) time. It can be a useful combinatorial explanation, but the at-most helper is shorter and generalizes naturally to any nonnegative array.

How would the solution answer many different goals for the same array?

Running the linear scan separately for each query costs O(nq) for q goals. Because the input is binary, no subarray sum can exceed the total number of ones, so queries outside that range return zero immediately. If the number of queries is modest, repeated scans are usually the clearest option and preserve O(1) working space per query.

For a very large batch, precomputing the answer for every possible sum may be worthwhile, but a naive precomputation is still quadratic. Faster correlation-based methods can derive all counts from the gaps between ones, though they add substantial implementation complexity and are justified only when the batch size dominates the array length.

How could the algorithm return the matching index ranges instead of only their count?

Use prefix sums mapped to lists of indices rather than frequencies. When the running sum is current_sum, every stored index for current_sum - goal forms a valid range ending at the current position. Emit those pairs, then store the current prefix index.

The search work remains O(n) aside from producing results, while the total running time and output space become O(n + k) for k returned ranges. That output-sensitive cost is unavoidable because all k ranges must be materialized.

Can this be processed as a stream?

The prefix-sum method works online. It needs only the running sum, the answer so far, and the frequency map of earlier prefix sums; each arriving value can update the answer immediately. Space can still grow linearly with the number of distinct prefix sums.

The at-most subtraction can also maintain two windows online for a fixed goal: one constrained by goal and one by goal - 1. Their numbers of valid suffixes at each new right endpoint differ by the number of exact-sum subarrays ending there. This retains O(1) extra state for a binary stream, provided old values remain accessible until both left boundaries pass them; a queue may be needed when the stream itself is not stored.