Binary Subarrays With Sum

Medium
250.

Binary Subarrays With Sum

Binary Subarrays With Sum is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.

Given a binary array nums and an integer goal, return the number of non-empty subarrays whose sum equals goal.

Example 1

Input
nums = [1,0,1,0,1], goal = 2
Output
4
Explanation
The four subarrays are [1,0,1,_,_], [1,0,1,0,_], [_,0,1,0,1] and [_,_,1,0,1].

Example 2

Input
nums = [0,0,0,0,0], goal = 0
Output
15
Explanation
Every one of the 15 subarrays sums to zero.

Example 3

Input
nums = [1,1], goal = 1
Output
2

Constraints

  • 1 <= nums.length <= 40
  • nums[i] is 0 or 1.
  • 0 <= goal <= nums.length

Follow-up: The zeros make a plain sliding window awkward. What does a prefix-sum hash map give you?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} goal
 * @return {number}
 */
var numSubarraysWithSum = function(nums, goal) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Binary Subarrays With Sum — Solution in Python, Java & C++

Binary Subarrays With Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Binary Subarrays With Sum is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon and Google interviews.

Problem statement

Given a binary array nums and an integer goal, return the number of non-empty subarrays whose sum equals goal.

Example 1

Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The four subarrays are [1,0,1,_,_], [1,0,1,0,_], [_,0,1,0,1] and [_,_,1,0,1].

Example 2

Input: nums = [0,0,0,0,0], goal = 0
Output: 15
Explanation: Every one of the 15 subarrays sums to zero.

Example 3

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

Constraints

  • 1 <= nums.length <= 40
  • nums[i] is 0 or 1.
  • 0 <= goal <= nums.length

Follow-up: The zeros make a plain sliding window awkward. What does a prefix-sum hash map give you?

Hints for Binary Subarrays With Sum

  1. Hint 1

    Count prefix sums: a subarray summing to goal ends at i for every earlier prefix equal to prefix[i] - goal.

  2. Hint 2

    Seed the map with {0: 1} so subarrays starting at index 0 are counted.

  3. Hint 3

    The runs of zeros are exactly why the counting approach beats a two-pointer window here.

How to solve Binary Subarrays With Sum

Count prefix sums: a subarray ending at i sums to goal for every earlier prefix equal to prefix[i] - goal. Seed the map with {0: 1} for subarrays starting at index 0.

Approach

  1. Maintain count[prefix] starting with {0: 1}.
  2. For each element, update the running total and add count[total - goal] to the answer.
  3. Increment count[total].

Why it works

Every subarray is a difference of two prefixes; counting how many earlier prefixes give the right difference counts every valid subarray ending here exactly once.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • A two-pointer window struggles here because runs of zeros make many subarrays share a sum; atMost(goal) - atMost(goal - 1) is the window-based alternative.

Reference solution

Python

def numSubarraysWithSum(nums, goal: int) -> int:
    count = {0: 1}
    total = answer = 0
    for x in nums:
        total += x
        answer += count.get(total - goal, 0)
        count[total] = count.get(total, 0) + 1
    return answer

Java

public static int numSubarraysWithSum(int[] nums, int goal) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);
    int sum = 0, total = 0;
    for (int v : nums) {
        sum += v;
        total += count.getOrDefault(sum - goal, 0);
        count.put(sum, count.getOrDefault(sum, 0) + 1);
    }
    return total;
}

C++

int numSubarraysWithSum(vector<int>& nums, int goal) {
    unordered_map<int, int> count;
    count[0] = 1;
    int sum = 0, total = 0;
    for (int v : nums) {
        sum += v;
        auto it = count.find(sum - goal);
        if (it != count.end()) total += it->second;
        count[sum]++;
    }
    return total;
}

JavaScript

var numSubarraysWithSum = function(nums, goal) {
    const count = new Map();
    count.set(0, 1);
    let sum = 0, total = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        total += count.get(sum - goal) || 0;
        count.set(sum, (count.get(sum) || 0) + 1);
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets