# Binary Subarrays With Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/binary-subarrays-with-sum)
Canonical: https://scaleengineer.com/dsa/problems/binary-subarrays-with-sum
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
---
## Problem
Given a binary array `nums` and an integer `goal`, return _the number of non-empty **subarrays** with a sum_ `goal`.

A **subarray** is a contiguous part of the array.

**Example 1:**

**Input:** nums = [1,0,1,0,1], goal = 2
**Output:** 4
**Explanation:** The 4 subarrays are bolded and underlined below:
[**1,0,1**,0,1]
[**1,0,1,0**,1]
[1,**0,1,0,1**]
[1,0,**1,0,1**]

**Example 2:**

**Input:** nums = [0,0,0,0,0], goal = 0
**Output:** 15

**Constraints:**

* `1 <= nums.length <= 3 * 104`
* `nums[i]` is either `0` or `1`.
* `0 <= goal <= nums.length`

# Approaches
## Brute Force Enumeration
The most straightforward approach is to generate every possible non-empty subarray, calculate the sum of each one, and count how many of them have a sum equal to the `goal`. This can be done by iterating through all possible start and end indices of a subarray.
**Time:** O(N^2), where N is the length of the array. The two nested loops lead to a quadratic time complexity. For each pair of `(i, j)`, we do a constant amount of work. · **Space:** O(1). We only use a few variables to store the count and the current sum, requiring constant extra space.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** The quadratic time complexity makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on most platforms.
### Explanation
We use two nested loops to define the boundaries of all possible subarrays. The outer loop, with index `i`, iterates from the beginning to the end of the array, fixing the starting point of a subarray.

The inner loop, with index `j`, starts from `i` and goes to the end of the array, fixing the ending point. This defines the subarray `nums[i...j]`.

For each subarray `nums[i...j]`, we calculate its sum. A simple way to do this is to maintain a `currentSum` variable within the inner loop, which gets updated as `j` increases.

If the `currentSum` for the subarray `nums[i...j]` equals the `goal`, we increment a counter.

A small optimization can be made: since the array contains only non-negative numbers (0s and 1s), if the `currentSum` ever exceeds the `goal`, we can break out of the inner loop and move to the next starting point `i`, because adding more elements will only increase the sum further.

```java
class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int n = nums.length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                if (currentSum == goal) {
                    count++;
                }
                // Optimization: if sum exceeds goal, no need to extend the subarray
                if (currentSum > goal) {
                    break;
                }
            }
        }
        
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use a nested loop structure. The outer loop with index `i` iterates from `0` to `n-1` to select the starting element of the subarray.
- The inner loop with index `j` iterates from `i` to `n-1` to select the ending element of the subarray.
- For each subarray starting at `i`, maintain a `currentSum`.
- In the inner loop, add `nums[j]` to `currentSum`.
- If `currentSum` equals `goal`, increment the `count`.
- Since all numbers are non-negative, if `currentSum` exceeds `goal`, we can break the inner loop as further additions will only increase the sum.
- After both loops complete, return `count`.

## Prefix Sum with Hash Map
This is a standard and powerful technique for problems involving subarray sums. The sum of a subarray `nums[i...j]` can be calculated as `prefixSum[j] - prefixSum[i-1]`. We are looking for the number of pairs `(i, j)` such that `prefixSum[j] - prefixSum[i-1] = goal`. By rearranging the equation to `prefixSum[i-1] = prefixSum[j] - goal`, the problem transforms into finding, for each `j`, how many previous prefix sums match the required value `prefixSum[j] - goal`. A hash map is used to efficiently store and retrieve the frequencies of prefix sums encountered so far.
**Time:** O(N), where N is the length of the array. We iterate through the array once, and each hash map operation takes, on average, O(1) time. · **Space:** O(N). In the worst-case scenario, all prefix sums could be unique, requiring the hash map to store up to N+1 key-value pairs.
**Pros:** Very efficient time complexity of O(N).; It's a general approach that works for arrays with any integers (positive, negative, or zero), not just binary ones.
**Cons:** Requires extra space for the hash map, which can be up to O(N) in the worst case.
### Explanation
We iterate through the array, maintaining a `currentSum` which represents the prefix sum up to the current element. We use a hash map, `prefixSumFreq`, to store each prefix sum encountered and its frequency.

We initialize the map with `{0: 1}`. This is a crucial step to handle subarrays that start from index 0. If a prefix sum `currentSum` itself equals `goal`, then `currentSum - goal = 0`, and we need to find a "prefix sum" of 0 before the array starts, which we account for with this initial map entry.

For each element `num` in `nums`:
1. Update `currentSum += num`.
2. We need to find how many times the prefix sum `currentSum - goal` has occurred before. Let's call this `complement`.
3. We look up `complement` in our `prefixSumFreq` map. The value associated with it, if any, is the number of subarrays ending at the current position with the desired sum. We add this value to our total `count`.
4. We then update the frequency of the `currentSum` in the map, incrementing its count or adding it if it's new.

After iterating through the entire array, `count` will hold the total number of subarrays with a sum equal to `goal`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int count = 0;
        int currentSum = 0;
        Map<Integer, Integer> prefixSumFreq = new HashMap<>();
        // Base case: a sum of 0 has been seen once (the empty prefix)
        prefixSumFreq.put(0, 1);

        for (int num : nums) {
            currentSum += num;
            int complement = currentSum - goal;
            
            // Check if a prefix sum exists that can be subtracted to get the goal
            count += prefixSumFreq.getOrDefault(complement, 0);
            
            // Add the current prefix sum to the map
            prefixSumFreq.put(currentSum, prefixSumFreq.getOrDefault(currentSum, 0) + 1);
        }
        
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0` and `currentSum = 0`.
- Create a hash map `prefixSumFreq` to store frequencies of prefix sums.
- Put an initial entry `(0, 1)` into `prefixSumFreq`. This handles cases where a subarray starting from index 0 has the target sum.
- Iterate through each `num` in the `nums` array:
  - Update `currentSum += num`.
  - Calculate the needed `complement = currentSum - goal`.
  - Add the frequency of this `complement` from the map to our `count`: `count += prefixSumFreq.getOrDefault(complement, 0)`.
  - Update the frequency of the `currentSum` in the map: `prefixSumFreq.put(currentSum, prefixSumFreq.getOrDefault(currentSum, 0) + 1)`.
- Return `count`.

## Sliding Window (At Most K)
This approach leverages the fact that the array contains non-negative numbers, which means the prefix sums are non-decreasing. This property allows us to use a sliding window. The core idea is to rephrase the problem: the number of subarrays with a sum of exactly `goal` is equal to the number of subarrays with a sum of *at most* `goal` minus the number of subarrays with a sum of *at most* `goal - 1`. We can implement a helper function, `atMost(k)`, using a standard sliding window pattern to count subarrays with a sum at most `k`. The final answer is then `atMost(goal) - atMost(goal - 1)`.
**Time:** O(N). The `atMost` function is called twice. In each call, the `right` pointer moves from left to right once, and the `left` pointer also moves from left to right once. Thus, each call takes O(N) time. Total time is O(N) + O(N) = O(N). · **Space:** O(1). We only use a few variables to store the pointers and the current sum.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1), making it more memory-efficient than the hash map approach.
**Cons:** The logic of converting 'exactly k' to 'at most k - at most k-1' can be less intuitive than a direct approach.; This specific approach relies on the array containing non-negative numbers.
### Explanation
The main function `numSubarraysWithSum` will call a helper function `atMost(k)` twice.

`return atMost(nums, goal) - atMost(nums, goal - 1);`

The `atMost(nums, k)` function works as follows:
- If `k < 0`, return 0, as no subarray can have a negative sum.
- Initialize `count = 0`, `left = 0`, and `currentSum = 0`.
- Iterate through the array with a `right` pointer from `0` to `nums.length - 1`.
- In each iteration, add `nums[right]` to `currentSum`.
- While `currentSum` is greater than `k`, shrink the window from the left by subtracting `nums[left]` and incrementing `left`.
- After the `while` loop, the window `[left...right]` has a sum of at most `k`.
- Any subarray that ends at `right` and starts at an index `s` where `left <= s <= right` will also have a sum of at most `k`.
- The number of such starting positions is `right - left + 1`.
- Add this number to our total `count`.
- After the loop finishes, `count` will hold the total number of subarrays with a sum of at most `k`.

```java
class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        return atMost(nums, goal) - atMost(nums, goal - 1);
    }

    private int atMost(int[] nums, int k) {
        if (k < 0) {
            return 0;
        }
        int count = 0;
        int left = 0;
        int currentSum = 0;
        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];
            while (currentSum > k) {
                currentSum -= nums[left];
                left++;
            }
            // All subarrays ending at 'right' with start >= 'left' have sum <= k.
            // The number of such subarrays is (right - left + 1).
            count += (right - left + 1);
        }
        return count;
    }
}
```
### Algorithm
- The main function `numSubarraysWithSum(nums, goal)` will return the result of `atMost(nums, goal) - atMost(nums, goal - 1)`.
- Define a helper function `atMost(nums, k)`:
  - Handle the edge case: if `k < 0`, return 0.
  - Initialize `count = 0`, `left = 0`, `sum = 0`.
  - Loop `right` from `0` to `nums.length - 1`:
    - Add `nums[right]` to `sum`.
    - While `sum > k`, shrink the window from the left: `sum -= nums[left]` and `left++`.
    - At this point, any subarray ending at `right` with a start index between `left` and `right` (inclusive) has a sum at most `k`. The number of such subarrays is `right - left + 1`.
    - Add `right - left + 1` to `count`.
  - Return `count`.

# Solutions
### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} goal * @return {number} */ var numSubarraysWithSum = function ( nums , goal ) { let i1 = 0 , i2 = 0 , s1 = 0 , s2 = 0 , j = 0 , ans = 0 ; const n = nums . length ; while ( j < n ) { s1 += nums [ j ]; s2 += nums [ j ]; while ( i1 <= j && s1 > goal ) s1 -= nums [ i1 ++ ]; while ( i2 <= j && s2 >= goal ) s2 -= nums [ i2 ++ ]; ans += i2 - i1 ; ++ j ; } return ans ; };
```

### Java

```java
class Solution {
public
  int numSubarraysWithSum(int[] nums, int goal) {
    int i1 = 0, i2 = 0, s1 = 0, s2 = 0, j = 0, ans = 0;
    int n = nums.length;
    while (j < n) {
      s1 += nums[j];
      s2 += nums[j];
      while (i1 <= j && s1 > goal) {
        s1 -= nums[i1++];
      }
      while (i2 <= j && s2 >= goal) {
        s2 -= nums[i2++];
      }
      ans += i2 - i1;
      ++j;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int numSubarraysWithSum ( vector < int >& nums , int goal ) { int i1 = 0 , i2 = 0 , s1 = 0 , s2 = 0 , j = 0 , ans = 0 ; int n = nums . size (); while ( j < n ) { s1 += nums [ j ]; s2 += nums [ j ]; while ( i1 <= j && s1 > goal ) s1 -= nums [ i1 ++ ]; while ( i2 <= j && s2 >= goal ) s2 -= nums [ i2 ++ ]; ans += i2 - i1 ; ++ j ; } return ans ; } };
```

### Python

```python
class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: i1 = i2 = s1 = s2 = j = ans = 0 n = len(nums) while j < n: s1 += nums[j] s2 += nums[j] while i1 <= j and s1 > goal: s1 -= nums[i1] i1 += 1 while i2 <= j and s2 >= goal: s2 -= nums[i2] i2 += 1 ans += i2 - i1 j += 1 return ans

```