To solve Binary Subarrays With Sum, iterate through the array while maintaining a running prefix sum and a hash map counting occurrences of each sum. For each index, check how many prior prefix sums equal the current sum minus the goal. This approach leverages O(n) time and constant additional space to efficiently count all valid subarrays without redundant scanning or nested loops.
Problem Statement
Given a binary array nums and an integer goal, return the number of non-empty contiguous subarrays whose sum equals goal. Each subarray consists of consecutive elements from nums and must sum precisely to goal.
For example, if nums = [1,0,1,0,1] and goal = 2, there are exactly 4 subarrays that satisfy this condition. Constraints ensure nums contains only 0s and 1s, with array length up to 3 * 10^4 and goal between 0 and nums.length.
Examples
Example 1
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
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
Example details omitted.
Constraints
- 1 <= nums.length <= 3 * 104
- nums[i] is either 0 or 1.
- 0 <= goal <= nums.length
Solution Approach
Prefix Sum with Hash Map
Iterate through nums while maintaining a cumulative prefix sum. Use a hash map to count occurrences of each prefix sum. For each element, add the number of times (current prefix sum - goal) has occurred to the result.
Sliding Window Not Directly Applicable
A pure sliding window cannot handle zero elements flexibly, as zeros do not increase the sum. The hash-based prefix sum method accounts for zeros naturally, avoiding missed subarrays.
Single Pass Efficiency
Combine the prefix sum and hash counting in one pass. Update the hash map after evaluating each element to ensure all subarrays ending at the current index are counted, maintaining O(n) time and minimal extra space.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
The algorithm scans the array once (O(n)) and uses a hash map storing at most n prefix sums, but values are bounded by the cumulative sum range; space remains effectively O(1) for integer keys.
What Interviewers Usually Probe
- Checks if you can optimize counting subarrays without nested loops.
- May ask why sliding window alone fails when zeros exist.
- Looks for clear explanation of prefix sum mapping to goal counts.
Common Pitfalls or Variants
Common pitfalls
- Forgetting to initialize prefix sum count map with 0 sum seen once.
- Updating hash map before counting current subarrays can undercount.
- Misinterpreting zeros and ones leads to missing valid subarrays.
Follow-up variants
- Count subarrays with sum less than or equal to goal.
- Handle arrays with arbitrary integers, not just binary.
- Return all subarrays instead of counting them.
How GhostInterview Helps
- Provides exact prefix sum plus hash map implementation for counting subarrays.
- Highlights failure modes of naive sliding window with zeros.
- Optimizes time and space analysis tied to array scanning plus hash lookup pattern.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the key pattern for Binary Subarrays With Sum?
The main pattern is array scanning with prefix sum and hash map lookup to count all subarrays matching the goal sum.
Can a sliding window solve this problem alone?
No, zeros prevent a fixed-length sliding window from capturing all valid subarrays; prefix sums with hash mapping are needed.
How do I handle goal = 0?
Initialize the hash map with 0 sum counted once; this ensures subarrays summing to zero are correctly counted.
What is the time complexity of the optimal solution?
The solution runs in O(n) time with a single pass and maintains prefix sum counts in a hash map.
Are there variants of this problem?
Yes, you can modify it to count subarrays with sum less than or equal to a target or handle arbitrary integer arrays.
Need direct help with Binary Subarrays With Sum instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Binary Subarrays With Sum from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
The problem requires counting subarrays with exactly k odd numbers using an efficient array scanning approach.
Open problem page#1658 Minimum Operations to Reduce X to ZeroFind the minimum number of operations to reduce a value x to zero by removing elements from an array.
Open problem page#995 Minimum Number of K Consecutive Bit FlipsDetermine the minimum number of k-length consecutive bit flips needed to convert all zeros to ones in a binary array efficiently.
Open problem page