# LeetCode 930: Binary Subarrays With Sum

## Problem Restatement

We are given a binary array `nums` and an integer `goal`.

A binary array means every value is either:

```python
0
```

or:

```python
1
```

We need to count how many non-empty contiguous subarrays have sum exactly equal to `goal`.

A subarray must be continuous. We cannot skip elements.

The official statement asks for the number of non-empty subarrays whose sum is `goal`, where `nums` is binary. Example cases include `[1,0,1,0,1]` with `goal = 2`, which returns `4`, and `[0,0,0,0,0]` with `goal = 0`, which returns `15`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A binary array `nums` and an integer `goal` |
| Output | Number of non-empty subarrays with sum `goal` |
| Subarray | A contiguous part of the array |
| Values | Each `nums[i]` is `0` or `1` |

Function shape:

```python
class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        ...
```

## Examples

Example 1:

```python
nums = [1, 0, 1, 0, 1]
goal = 2
```

The valid subarrays are:

```text
[1, 0, 1]
[1, 0, 1, 0]
[0, 1, 0, 1]
[1, 0, 1]
```

There are `4` valid subarrays.

So the answer is:

```python
4
```

Example 2:

```python
nums = [0, 0, 0, 0, 0]
goal = 0
```

Every non-empty subarray has sum `0`.

There are:

```text
5 + 4 + 3 + 2 + 1 = 15
```

valid subarrays.

So the answer is:

```python
15
```

## First Thought: Check Every Subarray

The direct way is to try every starting index and every ending index.

For each start:

1. Keep a running sum.
2. Extend the end index one step at a time.
3. Count the subarray when the running sum equals `goal`.

Code:

```python
class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        n = len(nums)
        ans = 0

        for left in range(n):
            total = 0

            for right in range(left, n):
                total += nums[right]

                if total == goal:
                    ans += 1

        return ans
```

This is correct, but it checks too many subarrays.

There are `O(n^2)` subarrays, so this is too slow for large input.

## Key Insight

We can use prefix sums.

Let:

```python
prefix[i]
```

be the sum of the first `i` elements.

The sum of a subarray from `left` to `right` is:

```text
prefix[right + 1] - prefix[left]
```

We want this to equal `goal`.

So:

```text
prefix[right + 1] - prefix[left] = goal
```

Rearrange:

```text
prefix[left] = prefix[right + 1] - goal
```

This means that when we are at the current prefix sum, we only need to know how many earlier prefix sums equal:

```python
current_sum - goal
```

A hash map can store how many times each prefix sum has appeared.

## Algorithm

Create a map:

```python
count = {0: 1}
```

This means we have seen prefix sum `0` once before reading any element.

Then scan `nums`.

For each number:

1. Add it to `current`.
2. Compute `need = current - goal`.
3. Add `count[need]` to the answer.
4. Add the current prefix sum to the map.

The order matters.

We count earlier prefix sums before inserting the current prefix sum.

## Walkthrough

Use:

```python
nums = [1, 0, 1, 0, 1]
goal = 2
```

Start:

```python
count = {0: 1}
current = 0
ans = 0
```

| Index | Value | `current` | `need = current - goal` | Add to `ans` | `ans` |
|---:|---:|---:|---:|---:|---:|
| 0 | 1 | 1 | -1 | 0 | 0 |
| 1 | 0 | 1 | -1 | 0 | 0 |
| 2 | 1 | 2 | 0 | 1 | 1 |
| 3 | 0 | 2 | 0 | 1 | 2 |
| 4 | 1 | 3 | 1 | 2 | 4 |

The final answer is:

```python
4
```

The last step adds `2` because prefix sum `1` appeared twice earlier. Each earlier prefix sum gives one valid subarray ending at the current index.

## Correctness

The algorithm maintains a frequency map of all prefix sums seen before the current position.

At a current index, let the current prefix sum be `current`.

A subarray ending at this index has sum `goal` exactly when its starting prefix sum is:

```python
current - goal
```

The map tells us how many earlier positions have that prefix sum. Each such earlier position defines one distinct subarray ending at the current index with sum `goal`.

The algorithm adds exactly that number to the answer.

Then it records the current prefix sum so it can be used by future subarrays.

Every valid subarray has one ending index. When the scan reaches that ending index, the subarray's starting prefix sum is already in the map, so the subarray is counted.

No invalid subarray is counted, because the algorithm only adds prefixes that satisfy:

```text
current - earlier_prefix = goal
```

Therefore, the final answer is exactly the number of non-empty subarrays with sum `goal`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We scan `nums` once |
| Space | `O(n)` | The map may store up to `n + 1` prefix sums |

## Implementation

```python
from collections import defaultdict

class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        count = defaultdict(int)
        count[0] = 1

        current = 0
        ans = 0

        for num in nums:
            current += num

            need = current - goal
            ans += count[need]

            count[current] += 1

        return ans
```

## Code Explanation

We use a map from prefix sum to frequency:

```python
count = defaultdict(int)
count[0] = 1
```

The initial `0` handles subarrays that start at index `0`.

For example, if the current prefix sum is already equal to `goal`, then:

```python
current - goal == 0
```

So the initial prefix sum contributes one valid subarray.

We update the running prefix sum:

```python
current += num
```

Then we find the prefix sum needed to form a subarray with sum `goal`:

```python
need = current - goal
```

Every earlier occurrence of `need` gives one valid subarray ending here:

```python
ans += count[need]
```

Finally, we record the current prefix sum:

```python
count[current] += 1
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.numSubarraysWithSum([1, 0, 1, 0, 1], 2) == 4
    assert s.numSubarraysWithSum([0, 0, 0, 0, 0], 0) == 15
    assert s.numSubarraysWithSum([1, 1, 1], 2) == 2
    assert s.numSubarraysWithSum([1, 0, 0, 1], 1) == 6
    assert s.numSubarraysWithSum([0], 0) == 1
    assert s.numSubarraysWithSum([1], 0) == 0

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,0,1,0,1]`, goal `2` | Official example |
| All zeros, goal `0` | Many zero-sum subarrays |
| `[1,1,1]`, goal `2` | Consecutive ones |
| `[1,0,0,1]`, goal `1` | Zeros expand valid windows |
| `[0]`, goal `0` | Smallest valid zero case |
| `[1]`, goal `0` | No valid zero-sum subarray |