Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Binary Subarrays With Sum

MEDIUMProblemSolveExternal Links

Description

You are given a binary array nums (an array containing only 0s and 1s) and an integer goal.

Return the number of non-empty subarrays whose elements sum to exactly goal.

A subarray is a contiguous part of the array. For example, in the array [1, 0, 1], the subarrays are [1], [0], [1], [1, 0], [0, 1], and [1, 0, 1].

Since the array is binary, the sum of a subarray simply equals the count of 1s within that subarray. So you are effectively counting how many contiguous segments contain exactly goal ones.

Examples

Example 1

Input: nums = [1, 0, 1, 0, 1], goal = 2

Output: 4

Explanation: We need subarrays containing exactly two 1s. The four valid subarrays are:

  • [1, 0, 1] from index 0 to 2 (sum = 1 + 0 + 1 = 2)
  • [1, 0, 1, 0] from index 0 to 3 (sum = 1 + 0 + 1 + 0 = 2)
  • [0, 1, 0, 1] from index 1 to 4 (sum = 0 + 1 + 0 + 1 = 2)
  • [1, 0, 1] from index 2 to 4 (sum = 1 + 0 + 1 = 2)

Notice that trailing or leading zeros can extend a valid subarray without changing its sum, which is why we get multiple valid subarrays from the same set of 1s.

Example 2

Input: nums = [0, 0, 0, 0, 0], goal = 0

Output: 15

Explanation: Every subarray of an all-zeros array has sum 0, which equals the goal. The total number of non-empty subarrays in an array of length 5 is 5 × (5 + 1) / 2 = 15. Each one is valid because none of them contain any 1s, so every subarray sums to 0.

This edge case highlights that when goal is 0, we are counting subarrays that contain no 1s at all — only consecutive runs of 0s.

Constraints

  • 1 ≤ nums.length ≤ 3 × 10^4
  • nums[i] is either 0 or 1
  • 0 ≤ goal ≤ nums.length

Editorial

Brute Force

Intuition

The most natural way to solve this problem is to consider every possible subarray, compute its sum, and check whether it equals the goal.

Imagine you have a row of light switches, each either on (1) or off (0). You want to count how many contiguous groups of switches have exactly goal switches turned on. The brute force approach is to pick every possible starting switch, then extend the group one switch at a time to the right, keeping a running tally of how many are on. Every time your tally hits exactly goal, you count that group.

Since we only add one element at a time as we extend the subarray, we can maintain a running sum rather than recalculating from scratch. This turns each inner step into O(1) work, but we still check all O(n²) possible subarrays.

Step-by-Step Explanation

Let's trace through nums = [1, 0, 1, 0, 1], goal = 2:

Step 1: Initialize count = 0. Start outer loop with i = 0.

Step 2: i = 0, j = 0: sum = 1. Is 1 == 2? No.

Step 3: i = 0, j = 1: sum = 1 + 0 = 1. Is 1 == 2? No.

Step 4: i = 0, j = 2: sum = 1 + 1 = 2. Is 2 == 2? Yes! count = 1. Subarray [1, 0, 1].

Step 5: i = 0, j = 3: sum = 2 + 0 = 2. Is 2 == 2? Yes! count = 2. The trailing 0 doesn't change the sum.

Step 6: i = 0, j = 4: sum = 2 + 1 = 3. Is 3 == 2? No. We overshot — too many 1s.

Step 7: Move to i = 1, reset sum. j = 1: sum = 0. j = 2: sum = 1. j = 3: sum = 1. j = 4: sum = 0 + 1 + 0 + 1 = 2. count = 3.

Step 8: Move to i = 2. j = 2: sum = 1. j = 3: sum = 1. j = 4: sum = 1 + 0 + 1 = 2. count = 4.

Step 9: Move to i = 3. j = 3: sum = 0. j = 4: sum = 1. No matches.

Step 10: Move to i = 4. j = 4: sum = 1. No match.

Result: count = 4.

Brute Force — Checking All Subarrays — Watch how we fix a starting index i, then extend the ending index j rightward, accumulating a running sum. When sum equals goal, we count the subarray.

Algorithm

  1. Initialize count = 0
  2. For each starting index i from 0 to n - 1:
    • Initialize sum = 0
    • For each ending index j from i to n - 1:
      • Add nums[j] to sum
      • If sum == goal, increment count
  3. Return count

Code

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int n = nums.size();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum == goal) {
                    count++;
                }
            }
        }
        
        return count;
    }
};
class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        n = len(nums)
        count = 0
        
        for i in range(n):
            current_sum = 0
            for j in range(i, n):
                current_sum += nums[j]
                if current_sum == goal:
                    count += 1
        
        return count
class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int n = nums.length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum == goal) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times. For each starting index, the inner loop runs up to n times. In total we examine roughly n × (n + 1) / 2 subarrays. Each subarray check is O(1) since we maintain a running sum. With n up to 3 × 10^4, this means up to ~4.5 × 10^8 operations.

Space Complexity: O(1)

We only use a handful of integer variables (count, sum, i, j). No additional data structures are allocated.

Why This Approach Is Not Efficient

The brute force approach checks all O(n²) subarrays. With n up to 3 × 10^4, this results in approximately 4.5 × 10^8 operations, which is likely too slow for competitive programming time limits (typically around 10^8 operations per second).

The core inefficiency is that we are recomputing overlapping information. When we move the starting index from i to i+1, the subarrays starting at i+1 are a subset of what we already partially explored. We don't retain any knowledge about previously seen prefix sums.

Key insight: If we maintain a running prefix sum and remember how many times each prefix sum value has appeared, we can determine — in O(1) time — how many subarrays ending at the current position have a sum equal to the goal. This is the classic prefix sum + hash map technique.

Better Approach - Prefix Sum with Hash Map

Intuition

Think of prefix sums like a running odometer. The prefix sum at position i is the total number of 1s from the start of the array up to index i. If the prefix sum at index j is P[j] and at index i is P[i] (where i < j), then the sum of the subarray from i+1 to j is P[j] - P[i].

So we need to find pairs (i, j) where P[j] - P[i] = goal, which means P[i] = P[j] - goal.

Instead of searching backward for each j, we use a hash map that records how many times each prefix sum value has appeared so far. At each position j, we check: "How many earlier positions had a prefix sum of P[j] - goal?" The hash map answers this instantly in O(1).

We also pre-seed the map with {0: 1} to handle subarrays starting from index 0 (where the entire prefix from the start equals the goal).

Step-by-Step Explanation

Let's trace through nums = [1, 0, 1, 0, 1], goal = 2:

Step 1: Initialize: prefixSum = 0, count = 0, map = {0: 1}. The map entry {0: 1} means "the prefix sum 0 has occurred once" (before processing any element).

Step 2: Process index 0: nums[0] = 1. prefixSum = 0 + 1 = 1. Look up (1 - 2) = -1 in map. Not found — no subarray ending here has sum 2. Store prefixSum 1: map = {0: 1, 1: 1}.

Step 3: Process index 1: nums[1] = 0. prefixSum = 1 + 0 = 1. Look up (1 - 2) = -1. Not found. Update frequency of 1: map = {0: 1, 1: 2}.

Step 4: Process index 2: nums[2] = 1. prefixSum = 1 + 1 = 2. Look up (2 - 2) = 0. Found with frequency 1! That means 1 subarray ending at index 2 has sum 2 (the subarray from index 0 to 2). count = 0 + 1 = 1. Store prefixSum 2: map = {0: 1, 1: 2, 2: 1}.

Step 5: Process index 3: nums[3] = 0. prefixSum = 2 + 0 = 2. Look up (2 - 2) = 0. Found with frequency 1! count = 1 + 1 = 2. The valid subarray is from index 0 to 3. Update frequency of 2: map = {0: 1, 1: 2, 2: 2}.

Step 6: Process index 4: nums[4] = 1. prefixSum = 2 + 1 = 3. Look up (3 - 2) = 1. Found with frequency 2! That means 2 subarrays ending at index 4 have sum 2 (starting after the two positions where prefixSum was 1). count = 2 + 2 = 4. Store prefixSum 3: map = {0: 1, 1: 2, 2: 2, 3: 1}.

Result: count = 4.

Prefix Sum + Hash Map — One-Pass Counting — Watch how we compute a running prefix sum and use a hash map to instantly count how many previous prefix sums differ from the current one by exactly the goal.

Algorithm

  1. Initialize a hash map prefixCount with {0: 1} (the empty prefix has sum 0)
  2. Initialize prefixSum = 0 and count = 0
  3. For each element nums[i]:
    • Add nums[i] to prefixSum
    • Compute complement = prefixSum - goal
    • If complement exists in prefixCount, add prefixCount[complement] to count
    • Increment prefixCount[prefixSum] by 1
  4. Return count

Code

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        unordered_map<int, int> prefixCount;
        prefixCount[0] = 1;
        int prefixSum = 0;
        int count = 0;
        
        for (int num : nums) {
            prefixSum += num;
            int complement = prefixSum - goal;
            if (prefixCount.count(complement)) {
                count += prefixCount[complement];
            }
            prefixCount[prefixSum]++;
        }
        
        return count;
    }
};
class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        prefix_count = {0: 1}
        prefix_sum = 0
        count = 0
        
        for num in nums:
            prefix_sum += num
            complement = prefix_sum - goal
            if complement in prefix_count:
                count += prefix_count[complement]
            prefix_count[prefix_sum] = prefix_count.get(prefix_sum, 0) + 1
        
        return count
class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        Map<Integer, Integer> prefixCount = new HashMap<>();
        prefixCount.put(0, 1);
        int prefixSum = 0;
        int count = 0;
        
        for (int num : nums) {
            prefixSum += num;
            int complement = prefixSum - goal;
            if (prefixCount.containsKey(complement)) {
                count += prefixCount.get(complement);
            }
            prefixCount.put(prefixSum, prefixCount.getOrDefault(prefixSum, 0) + 1);
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array exactly once. At each step, we perform one hash map lookup and one hash map insertion, both of which are O(1) on average. Total: n iterations × O(1) work = O(n).

Space Complexity: O(n)

In the worst case, every prefix sum is unique, so the hash map stores up to n + 1 entries (including the initial {0: 1}). For a binary array with all 1s and goal = n, the prefix sums are 0, 1, 2, ..., n — all distinct — giving O(n) space.

Why This Approach Is Not Efficient

The prefix sum + hash map approach achieves optimal O(n) time, but it uses O(n) extra space for the hash map. For very large inputs close to the constraint limit (3 × 10^4), this is manageable, but we can do better.

The key observation is that our array is binary — it only contains 0s and 1s. This means all values are non-negative, and the prefix sum is monotonically non-decreasing. This special property enables a sliding window approach.

For general arrays with negative numbers, a sliding window would not work because shrinking the window from the left might increase or decrease the sum unpredictably. But with only non-negative values, shrinking the window always reduces (or maintains) the sum, making the window behavior predictable. This lets us eliminate the hash map entirely and achieve O(1) space.

Optimal Approach - Sliding Window

Intuition

Directly counting subarrays with exactly a given sum using a sliding window is tricky because the window can have the exact sum at multiple sizes. The elegant trick is to decompose the problem:

exactly(goal) = atMost(goal) − atMost(goal − 1)

The function atMost(k) counts how many subarrays have a sum less than or equal to k. This is a standard sliding window problem: expand the right end, and whenever the window sum exceeds k, shrink from the left. At each right position, the number of valid subarrays ending there is (right − left + 1) — one for each possible starting position within the window.

By subtracting atMost(goal − 1) from atMost(goal), we remove all subarrays with sum strictly less than goal, leaving only those with sum exactly equal to goal.

Imagine counting how many groups of friends have exactly 2 tall people. Instead of checking each group, you count groups with at most 2 tall people (easier to track as you scan), then subtract groups with at most 1 tall person. What remains are exactly the groups with precisely 2.

Step-by-Step Explanation

Let's trace through nums = [1, 0, 1, 0, 1], goal = 2.

We need to compute atMost(2) and atMost(1), then subtract.

--- Computing atMost(2) ---

Step 1: Initialize left = 0, sum = 0, total = 0.

Step 2: right = 0: sum = 0 + 1 = 1. Is 1 ≤ 2? Yes. Subarrays ending at 0: [1]. Contribute (0 - 0 + 1) = 1. total = 1.

Step 3: right = 1: sum = 1 + 0 = 1. Is 1 ≤ 2? Yes. Subarrays ending at 1: [1,0], [0]. Contribute 2. total = 3.

Step 4: right = 2: sum = 1 + 1 = 2. Is 2 ≤ 2? Yes. Subarrays ending at 2: [1,0,1], [0,1], [1]. Contribute 3. total = 6.

Step 5: right = 3: sum = 2 + 0 = 2. Is 2 ≤ 2? Yes. Subarrays ending at 3: [1,0,1,0], [0,1,0], [1,0], [0]. Contribute 4. total = 10.

Step 6: right = 4: sum = 2 + 1 = 3. Is 3 ≤ 2? No! Shrink: remove nums[0] = 1, left = 1, sum = 2. Now 2 ≤ 2. Subarrays ending at 4: [0,1,0,1], [1,0,1], [0,1], [1]. Contribute 4. total = 14.

atMost(2) = 14

--- Computing atMost(1) ---

Step 7: Reset left = 0, sum = 0, total = 0.

Step 8: right = 0: sum = 1. 1 ≤ 1? Yes. Contribute 1. total = 1.

Step 9: right = 1: sum = 1. 1 ≤ 1? Yes. Contribute 2. total = 3.

Step 10: right = 2: sum = 2. 2 ≤ 1? No! Shrink: remove 1, left = 1, sum = 1. Contribute 2. total = 5.

Step 11: right = 3: sum = 1. 1 ≤ 1? Yes. Contribute 3. total = 8.

Step 12: right = 4: sum = 2. 2 ≤ 1? No! Shrink: remove 0, left = 2, sum = 2. Still > 1. Shrink again: remove 1, left = 3, sum = 1. Contribute 2. total = 10.

atMost(1) = 10

Result: exactly(2) = atMost(2) − atMost(1) = 14 − 10 = 4.

Sliding Window — atMost(goal) Pass — Watch how the sliding window expands rightward and shrinks from the left when the sum exceeds the limit. At each right position, the window size tells us how many valid subarrays end there.

Algorithm

  1. Define a helper function atMost(k):
    • If k < 0, return 0 (no valid subarrays possible)
    • Initialize left = 0, sum = 0, count = 0
    • For each right from 0 to n - 1:
      • Add nums[right] to sum
      • While sum > k: subtract nums[left] from sum, increment left
      • Add (right - left + 1) to count
    • Return count
  2. Return atMost(goal) - atMost(goal - 1)

Code

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        return atMost(nums, goal) - atMost(nums, goal - 1);
    }
    
private:
    int atMost(vector<int>& nums, int k) {
        if (k < 0) return 0;
        
        int left = 0, sum = 0, count = 0;
        
        for (int right = 0; right < nums.size(); right++) {
            sum += nums[right];
            while (sum > k) {
                sum -= nums[left];
                left++;
            }
            count += right - left + 1;
        }
        
        return count;
    }
};
class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        def at_most(k: int) -> int:
            if k < 0:
                return 0
            
            left = 0
            current_sum = 0
            count = 0
            
            for right in range(len(nums)):
                current_sum += nums[right]
                while current_sum > k:
                    current_sum -= nums[left]
                    left += 1
                count += right - left + 1
            
            return count
        
        return at_most(goal) - at_most(goal - 1)
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 left = 0, sum = 0, count = 0;
        
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum > k) {
                sum -= nums[left];
                left++;
            }
            count += right - left + 1;
        }
        
        return count;
    }
}

Complexity Analysis

Time Complexity: O(n)

We call atMost twice, and each call does a single pass through the array. The left pointer only moves forward, so across the entire pass, each element is added once (when right reaches it) and removed at most once (when left passes it). This gives O(n) per call, and 2 × O(n) = O(n) total.

Space Complexity: O(1)

We use only a constant number of variables: left, sum, count, and right. No hash map, no auxiliary array — just pointers and running totals. This is the key improvement over the prefix sum approach which required O(n) space for the hash map.