Binary Subarrays With Sum
MedPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to generate every possible non-empty subarray, calculate the sum of each one, and count how many of them have a sum equal to the goal. This can be done by iterating through all possible start and end indices of a subarray.
Algorithm
- Initialize a counter
countto 0. - Use a nested loop structure. The outer loop with index
iiterates from0ton-1to select the starting element of the subarray. - The inner loop with index
jiterates fromiton-1to select the ending element of the subarray. - For each subarray starting at
i, maintain acurrentSum. - In the inner loop, add
nums[j]tocurrentSum. - If
currentSumequalsgoal, increment thecount. - Since all numbers are non-negative, if
currentSumexceedsgoal, we can break the inner loop as further additions will only increase the sum. - After both loops complete, return
count.
Walkthrough
We use two nested loops to define the boundaries of all possible subarrays. The outer loop, with index i, iterates from the beginning to the end of the array, fixing the starting point of a subarray.
The inner loop, with index j, starts from i and goes to the end of the array, fixing the ending point. This defines the subarray nums[i...j].
For each subarray nums[i...j], we calculate its sum. A simple way to do this is to maintain a currentSum variable within the inner loop, which gets updated as j increases.
If the currentSum for the subarray nums[i...j] equals the goal, we increment a counter.
A small optimization can be made: since the array contains only non-negative numbers (0s and 1s), if the currentSum ever exceeds the goal, we can break out of the inner loop and move to the next starting point i, because adding more elements will only increase the sum further.
class Solution { public int numSubarraysWithSum(int[] nums, int goal) { int n = nums.length; int count = 0; for (int i = 0; i < n; i++) { int currentSum = 0; for (int j = i; j < n; j++) { currentSum += nums[j]; if (currentSum == goal) { count++; } // Optimization: if sum exceeds goal, no need to extend the subarray if (currentSum > goal) { break; } } } return count; }}Complexity
Time
O(N^2), where N is the length of the array. The two nested loops lead to a quadratic time complexity. For each pair of `(i, j)`, we do a constant amount of work.
Space
O(1). We only use a few variables to store the count and the current sum, requiring constant extra space.
Trade-offs
Pros
Simple to understand and implement.
Uses constant extra space.
Cons
The quadratic time complexity makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on most platforms.
This is a standard and powerful technique for problems involving subarray sums. The sum of a subarray nums[i...j] can be calculated as prefixSum[j] - prefixSum[i-1]. We are looking for the number of pairs (i, j) such that prefixSum[j] - prefixSum[i-1] = goal. By rearranging the equation to prefixSum[i-1] = prefixSum[j] - goal, the problem transforms into finding, for each j, how many previous prefix sums match the required value prefixSum[j] - goal. A hash map is used to efficiently store and retrieve the frequencies of prefix sums encountered so far.
Algorithm
- Initialize
count = 0andcurrentSum = 0. - Create a hash map
prefixSumFreqto store frequencies of prefix sums. - Put an initial entry
(0, 1)intoprefixSumFreq. This handles cases where a subarray starting from index 0 has the target sum. - Iterate through each
numin thenumsarray:- Update
currentSum += num. - Calculate the needed
complement = currentSum - goal. - Add the frequency of this
complementfrom the map to ourcount:count += prefixSumFreq.getOrDefault(complement, 0). - Update the frequency of the
currentSumin the map:prefixSumFreq.put(currentSum, prefixSumFreq.getOrDefault(currentSum, 0) + 1).
- Update
- Return
count.
Walkthrough
We iterate through the array, maintaining a currentSum which represents the prefix sum up to the current element. We use a hash map, prefixSumFreq, to store each prefix sum encountered and its frequency.
We initialize the map with {0: 1}. This is a crucial step to handle subarrays that start from index 0. If a prefix sum currentSum itself equals goal, then currentSum - goal = 0, and we need to find a "prefix sum" of 0 before the array starts, which we account for with this initial map entry.
For each element num in nums:
- Update
currentSum += num. - We need to find how many times the prefix sum
currentSum - goalhas occurred before. Let's call thiscomplement. - We look up
complementin ourprefixSumFreqmap. The value associated with it, if any, is the number of subarrays ending at the current position with the desired sum. We add this value to our totalcount. - We then update the frequency of the
currentSumin the map, incrementing its count or adding it if it's new.
After iterating through the entire array, count will hold the total number of subarrays with a sum equal to goal.
import java.util.HashMap;import java.util.Map; class Solution { public int numSubarraysWithSum(int[] nums, int goal) { int count = 0; int currentSum = 0; Map<Integer, Integer> prefixSumFreq = new HashMap<>(); // Base case: a sum of 0 has been seen once (the empty prefix) prefixSumFreq.put(0, 1); for (int num : nums) { currentSum += num; int complement = currentSum - goal; // Check if a prefix sum exists that can be subtracted to get the goal count += prefixSumFreq.getOrDefault(complement, 0); // Add the current prefix sum to the map prefixSumFreq.put(currentSum, prefixSumFreq.getOrDefault(currentSum, 0) + 1); } return count; }}Complexity
Time
O(N), where N is the length of the array. We iterate through the array once, and each hash map operation takes, on average, O(1) time.
Space
O(N). In the worst-case scenario, all prefix sums could be unique, requiring the hash map to store up to N+1 key-value pairs.
Trade-offs
Pros
Very efficient time complexity of O(N).
It's a general approach that works for arrays with any integers (positive, negative, or zero), not just binary ones.
Cons
Requires extra space for the hash map, which can be up to O(N) in the worst case.
This approach leverages the fact that the array contains non-negative numbers, which means the prefix sums are non-decreasing. This property allows us to use a sliding window. The core idea is to rephrase the problem: the number of subarrays with a sum of exactly goal is equal to the number of subarrays with a sum of at most goal minus the number of subarrays with a sum of at most goal - 1. We can implement a helper function, atMost(k), using a standard sliding window pattern to count subarrays with a sum at most k. The final answer is then atMost(goal) - atMost(goal - 1).
Algorithm
- The main function
numSubarraysWithSum(nums, goal)will return the result ofatMost(nums, goal) - atMost(nums, goal - 1). - Define a helper function
atMost(nums, k):- Handle the edge case: if
k < 0, return 0. - Initialize
count = 0,left = 0,sum = 0. - Loop
rightfrom0tonums.length - 1:- Add
nums[right]tosum. - While
sum > k, shrink the window from the left:sum -= nums[left]andleft++. - At this point, any subarray ending at
rightwith a start index betweenleftandright(inclusive) has a sum at mostk. The number of such subarrays isright - left + 1. - Add
right - left + 1tocount.
- Add
- Return
count.
- Handle the edge case: if
Walkthrough
The main function numSubarraysWithSum will call a helper function atMost(k) twice.
return atMost(nums, goal) - atMost(nums, goal - 1);
The atMost(nums, k) function works as follows:
- If
k < 0, return 0, as no subarray can have a negative sum. - Initialize
count = 0,left = 0, andcurrentSum = 0. - Iterate through the array with a
rightpointer from0tonums.length - 1. - In each iteration, add
nums[right]tocurrentSum. - While
currentSumis greater thank, shrink the window from the left by subtractingnums[left]and incrementingleft. - After the
whileloop, the window[left...right]has a sum of at mostk. - Any subarray that ends at
rightand starts at an indexswhereleft <= s <= rightwill also have a sum of at mostk. - The number of such starting positions is
right - left + 1. - Add this number to our total
count. - After the loop finishes,
countwill hold the total number of subarrays with a sum of at mostk.
class Solution { public int numSubarraysWithSum(int[] nums, int goal) { return atMost(nums, goal) - atMost(nums, goal - 1); } private int atMost(int[] nums, int k) { if (k < 0) { return 0; } int count = 0; int left = 0; int currentSum = 0; for (int right = 0; right < nums.length; right++) { currentSum += nums[right]; while (currentSum > k) { currentSum -= nums[left]; left++; } // All subarrays ending at 'right' with start >= 'left' have sum <= k. // The number of such subarrays is (right - left + 1). count += (right - left + 1); } return count; }}Complexity
Time
O(N). The `atMost` function is called twice. In each call, the `right` pointer moves from left to right once, and the `left` pointer also moves from left to right once. Thus, each call takes O(N) time. Total time is O(N) + O(N) = O(N).
Space
O(1). We only use a few variables to store the pointers and the current sum.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1), making it more memory-efficient than the hash map approach.
Cons
The logic of converting 'exactly k' to 'at most k - at most k-1' can be less intuitive than a direct approach.
This specific approach relies on the array containing non-negative numbers.
Solutions
Solution
/** * @param {number[]} nums * @param {number} goal * @return {number} */ var numSubarraysWithSum = function ( nums , goal ) { let i1 = 0 , i2 = 0 , s1 = 0 , s2 = 0 , j = 0 , ans = 0 ; const n = nums . length ; while ( j < n ) { s1 += nums [ j ]; s2 += nums [ j ]; while ( i1 <= j && s1 > goal ) s1 -= nums [ i1 ++ ]; while ( i2 <= j && s2 >= goal ) s2 -= nums [ i2 ++ ]; ans += i2 - i1 ; ++ j ; } return ans ; };class Solution {public int numSubarraysWithSum(int[] nums, int goal) { int i1 = 0, i2 = 0, s1 = 0, s2 = 0, j = 0, ans = 0; int n = nums.length; while (j < n) { s1 += nums[j]; s2 += nums[j]; while (i1 <= j && s1 > goal) { s1 -= nums[i1++]; } while (i2 <= j && s2 >= goal) { s2 -= nums[i2++]; } ans += i2 - i1; ++j; } return ans; }}class Solution { public: int numSubarraysWithSum ( vector < int >& nums , int goal ) { int i1 = 0 , i2 = 0 , s1 = 0 , s2 = 0 , j = 0 , ans = 0 ; int n = nums . size (); while ( j < n ) { s1 += nums [ j ]; s2 += nums [ j ]; while ( i1 <= j && s1 > goal ) s1 -= nums [ i1 ++ ]; while ( i2 <= j && s2 >= goal ) s2 -= nums [ i2 ++ ]; ans += i2 - i1 ; ++ j ; } return ans ; } };class Solution: def numSubarraysWithSum(self, nums: List[int], goal: int) -> int: i1 = i2 = s1 = s2 = j = ans = 0 n = len(nums) while j < n: s1 += nums[j] s2 += nums[j] while i1 <= j and s1 > goal: s1 -= nums[i1] i1 += 1 while i2 <= j and s2 >= goal: s2 -= nums[i2] i2 += 1 ans += i2 - i1 j += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.