Binary Subarrays With Sum solution and explanation
Google
TCS
9 more videos on this problem
L9. Binary Subarrays With Sum | 2 Pointers and Sliding Window Playlisttake U forward · 20:27 · 324K views
Binary Subarrays with Sum - Leetcode 930 - PythonNeetCodeIO · 9:57 · 30K views
Binary Subarrays With Sum | 2 Approaches | Detailed Explanation | Leetcode 930 | codestorywithMIKcodestorywithMIK · 36:48 · 24K views
930. Binary Subarrays With Sum | 560. Subarray Sum Equals K | Prefix Sums | 2 Pointer Crash CourseAryan Mittal · 35:27 · 20K views
LeetCode 930 Solution in HIndi | LeetCode Binary Subarrays With Sum SolutionEngineering Digest · 5:49 · 9K views
930. Binary Subarrays with sum | leetcode daily challenge | DSA | Shashwat HindiShashCode · 18:24 · 5K views
LeetCode 930. [Medium] Binary Subarrays With SumFrancesco Manicardi · 4:09 · 2K views
LeetCode 930. Binary Subarrays With Sum Solution Explained - JavaAlgorithms and Data Structures Course · 6:49 · 2K views
Daily LeetCode Challenge: 930. Binary Subarrays With Sum | C++ | 2-Approaches | @shwetabhagat8920SHWETA BHAGAT · 36:12 · 755 views
Leetcode 930 | Binary Subarrays With Sum | Sliding Window Study Placement · 11:18 · 390 views
The 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 * 104nums[i]is either0or1.0 <= goal <= nums.length
Approach overview
Problem Overview: You are given a binary array nums and an integer goal. The task is to count how many contiguous subarrays have a sum exactly equal to goal. Because the array only contains 0 and 1, the total sum of any subarray equals the number of ones inside it.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Check every possible subarray. Start at each index, extend the subarray to the right, and maintain a running sum. Each time the sum equals goal, increment the count. This approach simply iterates through all start and end pairs, which leads to quadratic time. It works for small inputs but becomes slow when n grows because there are roughly n² / 2 subarrays to examine.
Approach 2: Prefix Sum with Hash Map (O(n) time, O(n) space)
This method uses the prefix sum idea combined with a hash table. Maintain a running prefix sum while iterating through the array. If the current prefix sum is curr, then any previous prefix sum equal to curr - goal indicates a valid subarray ending at the current index. Store counts of prefix sums in a hash map so lookups are constant time. For every element, update the running sum, check the map for curr - goal, and add that frequency to the answer. This approach handles all cases efficiently and works for any integer array, not just binary ones.
Approach 3: Sliding Window Using At-Most Trick (O(n) time, O(1) space)
Because the array contains only 0 and 1, you can use a sliding window technique. Instead of directly counting subarrays with sum equal to goal, compute atMost(goal) - atMost(goal - 1). The helper function counts subarrays with sum ≤ target using two pointers and a running window sum. Move the right pointer to expand the window and shrink from the left when the sum exceeds the limit. Each step adds the window length to the count, representing all valid subarrays ending at that index. The difference between the two counts gives exactly the number of subarrays with sum equal to goal.
Recommended for interviews: The prefix sum + hash map approach is the most common interview expectation because it demonstrates strong understanding of prefix sums and frequency maps. Mentioning the brute force approach first shows you understand the baseline solution. The sliding window trick is highly efficient for binary arrays and shows deeper insight into how array constraints can simplify the problem.
Approach 1: Prefix Sum with Hash Map
The prefix sum approach maintains a running sum and stores it in a hash map to efficiently count subarrays with a given sum. By keeping track of the number of times a particular sum has occurred, this method can determine how many subarrays sum to the desired goal by examining previous prefix sums. This solution is highly efficient as it leverages a linear pass through the array.
def numSubarraysWithSum(nums, goal):
prefix_sum = {0: 1}
curr_sum = 0
count = 0
for num in nums:
curr_sum += num
count += prefix_sum.get(curr_sum - goal, 0)
prefix_sum[curr_sum] = prefix_sum.get(curr_sum, 0) + 1
return countfunction numSubarraysWithSum(nums, goal) {
let prefixSumCount = new Map();
prefixSumCount.set(0, 1);
let currSum = 0;
let count = 0;
for (let num of nums) {
currSum += num;
count += prefixSumCount.get(currSum - goal) || 0;
prefixSumCount.set(currSum, (prefixSumCount.get(currSum) || 0) + 1);
}
return count;
}This solution uses a hash map to store prefix sums. As the array is traversed, the current sum is updated. For each element, it checks if curr_sum - goal exists in the hash map, which indicates a valid subarray sum, and updates the count accordingly.
Time Complexity: O(N) where N is the length of the array.
Space Complexity: O(N) for storing prefix sums.
Approach 2: Sliding Window
The sliding window technique incrementally builds a window of elements and checks if its sum matches the goal. Upon reaching or exceeding the goal sum, the window is adjusted by moving the left boundary to find more subarrays that might sum to the goal. This approach is useful for fixed-sum searches without repetitive recalculations.
public int numSubarraysWithSum(int[] nums, int goal) {
int start = 0, end = 0, sum = 0, count = 0;
while (end < nums.length) {
sum += nums[end];
while (sum > goal && start <= end) {
sum -= nums[start++];
}
if (sum == goal) {
count++;
int temp = start;
while (temp < end && nums[temp] == 0) {
count++;
temp++;
}
}
end++;
}
return count;
}#include <vector>
using namespace std;
int numSubarraysWithSum(vector<int>& nums, int goal) {
int start = 0, end = 0, sum = 0, count = 0;
while (end < nums.size()) {
sum += nums[end];
while (sum > goal && start <= end) {
sum -= nums[start++];
}
if (sum == goal) {
count++;
int temp = start;
while (temp < end && nums[temp] == 0) {
count++;
temp++;
}
}
end++;
}
return count;
}This Java implementation uses two pointers to define a sliding window. It increments the end pointer to expand the window until the sum exceeds the goal, then adjusts by incrementing start. It checks for additional valid subarrays by traversing zeros past start.
Time Complexity: O(N) where N is the length of the array.
Space Complexity: O(1) because no additional data structures are used.
Approach 3: Default Approach
func numSubarraysWithSum(nums []int, goal int) (ans int) {
cnt := map[int]int{0: 1}
s := 0
for _, v := range nums {
s += v
ans += cnt[s-goal]
cnt[s]++
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Prefix Sum with Hash Map | Time Complexity: O(N) where N is the length of the array. |
| Sliding Window | Time Complexity: O(N) where N is the length of the array. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Conceptual baseline or when input size is very small |
| Prefix Sum + Hash Map | O(n) | O(n) | General solution that works for binary and non-binary arrays |
| Sliding Window (At-Most Trick) | O(n) | O(1) | Best when the array contains only 0s and 1s |
Frequently asked questions
Is Binary Subarrays With Sum easy or hard?
Binary Subarrays With Sum is classified as a Medium problem on LeetCode with an acceptance rate around 68%. The challenge lies in recognizing the prefix sum pattern or the sliding window atMost trick that converts the problem into a linear-time solution.
Binary Subarrays With Sum Python/Java solution
Python and JavaScript implementations typically use the prefix sum plus hash map approach because dictionary lookups are straightforward and efficient. Java and C++ solutions often use the sliding window atMost technique for binary arrays since it runs in O(n) time and only uses constant extra space.
How to solve Binary Subarrays With Sum in O(n)?
Maintain a running prefix sum while iterating through the array and store frequencies of prefix sums in a hash map. For each index, check how many previous prefix sums equal currentSum - goal and add that count to the result. Another O(n) option for binary arrays is computing atMost(goal) minus atMost(goal - 1) using a sliding window.
What is the best approach for Binary Subarrays With Sum?
The prefix sum with hash map approach is the most widely used solution. It runs in O(n) time and O(n) space by storing counts of previous prefix sums and checking how many times curr - goal appears. For binary arrays specifically, a sliding window technique using the atMost trick can achieve O(n) time with O(1) space.
Is Binary Subarrays With Sum asked at Google/Amazon/Meta?
Binary Subarrays With Sum is a common interview-style problem involving prefix sums and sliding window techniques. Variants of subarray sum problems appear frequently in interviews at companies like Amazon, Google, and Meta because they test understanding of arrays, hashing, and linear-time optimization.
What data structure is used in Binary Subarrays With Sum?
The optimal prefix sum solution uses a hash map to store frequencies of prefix sums encountered so far. This allows constant-time lookup to determine how many previous prefixes produce the required subarray sum. The sliding window version relies on two pointers and a running sum instead of additional data structures.
What is the time complexity of Binary Subarrays With Sum?
The optimal solutions run in O(n) time where n is the length of the array. Prefix sum with a hash map processes each element once with constant-time lookups, while the sliding window approach moves each pointer at most n times. Both significantly outperform the O(n^2) brute force method.