Binary Subarrays With Sum - Solution & Explanation
Problem Statement
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.
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.
Code
Python
JavaScript
Complexity
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.
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.
Complexity
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
Code
Python
Java
C++
Go
JavaScript
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 | — |
Detailed 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 |
Video Solution
L9. Binary Subarrays With Sum | 2 Pointers and Sliding Window Playlist • take U forward • 324,595 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Binary Subarrays With Sum easy or hard?
Binary Subarrays With Sum Python/Java solution
How to solve Binary Subarrays With Sum in O(n)?
What is the best approach for Binary Subarrays With Sum?
Is Binary Subarrays With Sum asked at Google/Amazon/Meta?
What data structure is used in Binary Subarrays With Sum?
What is the time complexity of Binary Subarrays With Sum?
Ready to solve this problem?
Practice Binary Subarrays With Sum with our built-in code editor and test cases.
Practice on FleetCode