930. Binary Subarrays With Sum
Problem Description
Given a binary array, which consists of only 0's and 1's, and a target integer goal
, the task is to find the number of subarrays whose sum equals goal
. A subarray is defined as any continuous sequence of the array. The binary nature of the array means any sum of its subarray will also be an integer, making the problem about finding subarray sums that match the given integer.
Intuition
The solution employs a two-pointer approach that creates a sliding window of variable size over the array. Two pointers, i1
and i2
, are moved along the array to adjust the window size. Pointer j
is used to extend the window by moving right. The variables s1
and s2
are used to track the sums of numbers within the window.
- We use two sliding windows: one to find the number of subarrays with sum just over
goal
(s1
andi1
), and another to find the number of subarrays with sum equal to or just overgoal
(s2
andi2
). - As we move the main pointer
j
through the array, we increases1
ands2
by the new element included in the windownums[j]
. - Next, we need to shrink the windows if necessary. If
s1
is greater thangoal
, we movei1
to reduce the window and the sum. Similarly, ifs2
is greater or equal thangoal
, we movei2
. - The difference between
i2
andi1
gives us the number of new subarrays that have a sum equal togoal
considering the new elementnums[j]
. - We increment
ans
by this difference sincei2 - i1
represents the number of valid subarrays ending atj
with sum exactlygoal
. - We repeat this process for every element of the array by incrementing
j
, thus exploring every potential subarray.
Why does this work? The two sliding windows track the lower and upper bounds of sums around our goal
. By taking the difference of the counts, we effectively count only those subarrays whose sum is exactly goal
. Since we consider each subarray ending at various j
positions, we can ensure that all possible subarrays are counted.
With every increment of j
, we essentially say, "Given all the subarrays ending at j
, count how many have a sum of goal
." The sliding of i1
and i2
keeps the window's sum around goal
and accurately maintains the count.
This approach is efficient since it requires only a single pass through the array, leading to a time complexity of O(n), where n is the length of the input array nums
.
Learn more about Prefix Sum and Sliding Window patterns.
Solution Approach
The solution to the subarray sum problem implements a variation of the two-pointer technique which helps to optimize the search for subarrays that add up to the goal
. Here's a step-by-step explanation:
- Initialize two pairs of pointers
i1
,i2
and their corresponding sumss1
,s2
to0
. These will be used to manage two sliding windows. Also, initialize a pointerj
to extend the window andans
to accumulate the number of valid subarrays found. - Iterate over the array with the main pointer
j
. For each elementnums[j]
being considered:- Add
nums[j]
to boths1
ands2
, which represents attempting to add the current element to our current subarray sums.
- Add
- If
s1
exceeds thegoal
, shrink the first window:- Subtract
nums[i1]
froms1
and incrementi1
to reduce the window from the left, doing this untils1
is no longer greater thangoal
.
- Subtract
- Similarly, if
s2
is at least thegoal
, shrink the second window:- Subtract
nums[i2]
froms2
and incrementi2
to reduce the window from the left, doing this untils2
is smaller thangoal
.
- Subtract
- After adjusting both windows, calculate the number of new subarrays found:
- The difference
i2 - i1
tells us how many valid subarrays end atj
with the desired sumgoal
because those will be the subarrays contained within the window tracked byi2
but not yet byi1
. - Add this difference to
ans
which tallies our result.
- The difference
- Repeat steps 2 through 5 as you move the pointer
j
to the right until you've processed every element in the array. - Once the iteration is complete,
ans
holds the final count of subarrays whose sum is equal togoal
.
This code efficiently finds all subarrays with the desired sum in linear time, utilizing O(1)
extra space, excluding the input and output. The key ingredients of the solution are the two-pointer technique and a single pass, avoiding unnecessary recomputation.
No complex data structures are needed because the pointers and sums effectively manage the windows of potential subarrays. The algorithm iteratively adjusts these windows to find all valid subarrays in the most optimized manner.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Letās consider the binary array nums = [1, 0, 1, 0, 1]
and the target integer goal = 2
. We need to find the number of subarrays with the sum equal to goal
.
- We initialize pointers and sums:
i1 = i2 = 0
,s1 = s2 = 0
, andans = 0
. - Start iterating with pointer
j
from left to right. The main goal is to addnums[j]
to boths1
ands2
and then adjust the windows with pointersi1
andi2
.
Using the array provided, here's how the solution progresses:
- For
j = 0
(the first element is1
):s1 = s2 = 1
. No window adjustment needed since neithers1
nors2
is over thegoal
yet.
- For
j = 1
(the second element is0
):s1 = s2 = 1
. Still no adjustment as we are not over thegoal
.
- For
j = 2
(the third element is1
):s1 = s2 = 2
. Sinces2 >= goal
, we incrementi2
. Now,i2 = 1
ands2 = 1
(s1
remains2
because we have to exceedgoal
to adjusti1
).i2 - i1 = 1
. We found one valid subarray [1, 0, 1] and incrementans
by 1.
- For
j = 3
(the fourth element is0
):s1 = 2
ands2 = 1
. No adjustment required.
- For
j = 4
(the fifth element is1
):s1 = s2 = 2
. Both sums are equal to thegoal
.- Since
s1 == goal
, we incrementi1
. Now,i1 = 1
ands1 = 1
. - Similarly,
i2
also increments becauses2 >= goal
. Now,i2 = 3
ands2 = 0
. i2 - i1 = 2
. The two new valid subarrays are [1, 0, 1] and [0, 1] ending atj=4
. So we incrementans
by 2.
After iterating through the array, weāve found ans = 3
valid subarrays ([1, 0, 1], [1, 0, 1], and [0, 1]) where the sum matches the goal
.
Itās important to understand that the same subarray may be counted at different stages depending on the j
position. This method ensures that every unique subarray is considered without double counting, and the result is achieved with a single traversal.
Solution Implementation
1class Solution:
2 def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
3 left1 = left2 = sum1 = sum2 = idx = total_subarrays = 0
4 array_length = len(nums)
5
6 # Iterate over the array to find subarrays with sum equal to goal
7 while idx < array_length:
8 # Increase running sums with the current number
9 sum1 += nums[idx]
10 sum2 += nums[idx]
11
12 # Decrease sum1 until it's no more than goal by moving left1 pointer right
13 while left1 <= idx and sum1 > goal:
14 sum1 -= nums[left1]
15 left1 += 1
16
17 # Decrease sum2 until it's just less than goal by moving left2 pointer right
18 while left2 <= idx and sum2 >= goal:
19 sum2 -= nums[left2]
20 left2 += 1
21
22 # Add the number of new subarrays found to the total
23 total_subarrays += left2 - left1
24
25 # Move to the next element
26 idx += 1
27
28 return total_subarrays
29
1class Solution {
2 // Method to count the number of subarrays with a sum equal to the given goal.
3 public int numSubarraysWithSum(int[] nums, int goal) {
4 int left1 = 0, left2 = 0, sum1 = 0, sum2 = 0, right = 0, result = 0;
5 int n = nums.length;
6
7 // Iterate over the elements of the array using 'right' as the right end of the subarray.
8 while (right < n) {
9 // Increase sums by the current element.
10 sum1 += nums[right];
11 sum2 += nums[right];
12
13 // Shrink the window from the left (left1) until the sum (sum1) is not greater than the goal.
14 while (left1 <= right && sum1 > goal) {
15 sum1 -= nums[left1++];
16 }
17
18 // Shrink the window from the left (left2) until the sum (sum2) is not greater than or equal to the goal.
19 while (left2 <= right && sum2 >= goal) {
20 sum2 -= nums[left2++];
21 }
22
23 // The window between left2 and left1 contains all the starting points for subarrays ending at 'right'
24 // with sums that are exactly equal to the goal.
25 result += left2 - left1;
26
27 // Move to the next element.
28 ++right;
29 }
30
31 // Return total count of subarrays with a sum equal to the goal.
32 return result;
33 }
34}
35
1class Solution {
2public:
3 int numSubarraysWithSum(vector<int>& nums, int goal) {
4 int startIndexForStrictlyGreater = 0; // Start index for subarrays with sum strictly greater than goal
5 int startIndexForAtLeastGoal = 0; // Start index for subarrays with sum at least as much as goal
6 int sumForStrictlyGreater = 0; // Current sum for the subarrays which is strictly greater than goal
7 int sumForAtLeastGoal = 0; // Current sum for the subarrays which is at least as much as goal
8 int endIndex = 0; // Current end index of the subarray
9 int countSubarrays = 0; // Count of subarrays with sum exactly equals to goal
10 int numSize = nums.size(); // Size of the input array
11
12 // Iterate over each element in nums to find subarrays with sum equal to goal
13 while (endIndex < numSize) {
14 sumForStrictlyGreater += nums[endIndex]; // Increment sum by current element for strictly greater sum
15 sumForAtLeastGoal += nums[endIndex]; // Increment sum by current element for at least goal sum
16
17 // Move startIndexForStrictlyGreater till the sum is strictly greater than the goal
18 while (startIndexForStrictlyGreater <= endIndex && sumForStrictlyGreater > goal) {
19 sumForStrictlyGreater -= nums[startIndexForStrictlyGreater++];
20 }
21
22 // Move startIndexForAtLeastGoal till the sum is at least as much as the goal
23 while (startIndexForAtLeastGoal <= endIndex && sumForAtLeastGoal >= goal) {
24 sumForAtLeastGoal -= nums[startIndexForAtLeastGoal++];
25 }
26
27 // The number of subarrays which sum up to the goal equals to the difference of indices
28 // This gives us the count of all the subarrays between the two starts
29 countSubarrays += startIndexForAtLeastGoal - startIndexForStrictlyGreater;
30
31 // Move to the next element
32 ++endIndex;
33 }
34 return countSubarrays; // Return the total count of subarrays with sum equal to goal
35 }
36};
37
1/**
2 * Counts the number of subarrays with a sum equal to the given goal.
3 *
4 * @param {number[]} nums - The array of numbers to search within.
5 * @param {number} goal - The target sum for the subarrays.
6 * @return {number} The number of subarrays whose sum equals the goal.
7 */
8const numSubarraysWithSum = (nums: number[], goal: number): number => {
9 let leftIndexForStrict = 0, // Left index for the subarray where the sum is strictly more than the goal.
10 leftIndexForLoose = 0, // Left index for the subarray where the sum is at least the goal.
11 strictSum = 0, // Sum of the current subarray for the strict condition.
12 looseSum = 0, // Sum of the current subarray for the loose condition.
13 rightIndex = 0, // Right index of the subarray currently being considered.
14 count = 0; // The count of valid subarrays.
15 const length = nums.length;
16
17 // Traverse through the array using the right index.
18 while (rightIndex < length) {
19 // Add the current element to both the strict and loose sum.
20 strictSum += nums[rightIndex];
21 looseSum += nums[rightIndex];
22
23 // If the strict sum is greater than the goal, move the left index to reduce the sum.
24 while (leftIndexForStrict <= rightIndex && strictSum > goal) {
25 strictSum -= nums[leftIndexForStrict++];
26 }
27
28 // If the loose sum is at least the goal, move the left index to find the next valid subarray start.
29 while (leftIndexForLoose <= rightIndex && looseSum >= goal) {
30 looseSum -= nums[leftIndexForLoose++];
31 }
32
33 // The difference between leftIndexForLoose and leftIndexForStrict gives the count of subarrays where the sum equals the goal.
34 count += leftIndexForLoose - leftIndexForStrict;
35
36 // Move to the next element in the array.
37 ++rightIndex;
38 }
39
40 // Return the total count of valid subarrays.
41 return count;
42};
43
44// This function can now be called with TypeScript's type checking.
45
Time and Space Complexity
The code provided uses two pointers technique to keep track of subarrays with sums equal to or just above the goal. The time complexity of the code is O(n)
because the while loop runs for each element in the array (n
elements), and inside the loop, each pointer (i1 and i2) moves forward (never backwards), meaning each element is processed once.
The space complexity of the code is O(1)
as the space used does not grow with the input size n
. The variables i1
, i2
, s1
, s2
, j
, ans
, and n
use a constant amount of space.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we