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.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Prefix Sum, Sliding Window
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 40nums[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
Hint 1
Count prefix sums: a subarray summing to
goalends atifor every earlier prefix equal toprefix[i] - goal.Hint 2
Seed the map with
{0: 1}so subarrays starting at index 0 are counted.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
- Maintain
count[prefix]starting with{0: 1}. - For each element, update the running total and add
count[total - goal]to the answer. - 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 answerJava
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