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 and i1), and another to find the number of subarrays with sum equal to or just over goal (s2 and i2).
  • As we move the main pointer j through the array, we increase s1 and s2 by the new element included in the window nums[j].
  • Next, we need to shrink the windows if necessary. If s1 is greater than goal, we move i1 to reduce the window and the sum. Similarly, if s2 is greater or equal than goal, we move i2.
  • The difference between i2 and i1 gives us the number of new subarrays that have a sum equal to goal considering the new element nums[j].
  • We increment ans by this difference since i2 - i1 represents the number of valid subarrays ending at j with sum exactly goal.
  • 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:

  1. Initialize two pairs of pointers i1, i2 and their corresponding sums s1, s2 to 0. These will be used to manage two sliding windows. Also, initialize a pointer j to extend the window and ans to accumulate the number of valid subarrays found.
  2. Iterate over the array with the main pointer j. For each element nums[j] being considered:
    • Add nums[j] to both s1 and s2, which represents attempting to add the current element to our current subarray sums.
  3. If s1 exceeds the goal, shrink the first window:
    • Subtract nums[i1] from s1 and increment i1 to reduce the window from the left, doing this until s1 is no longer greater than goal.
  4. Similarly, if s2 is at least the goal, shrink the second window:
    • Subtract nums[i2] from s2 and increment i2 to reduce the window from the left, doing this until s2 is smaller than goal.
  5. After adjusting both windows, calculate the number of new subarrays found:
    • The difference i2 - i1 tells us how many valid subarrays end at j with the desired sum goal because those will be the subarrays contained within the window tracked by i2 but not yet by i1.
    • Add this difference to ans which tallies our result.
  6. Repeat steps 2 through 5 as you move the pointer j to the right until you've processed every element in the array.
  7. Once the iteration is complete, ans holds the final count of subarrays whose sum is equal to goal.

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 Evaluator

Example 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.

  1. We initialize pointers and sums: i1 = i2 = 0, s1 = s2 = 0, and ans = 0.
  2. Start iterating with pointer j from left to right. The main goal is to add nums[j] to both s1 and s2 and then adjust the windows with pointers i1 and i2.

Using the array provided, here's how the solution progresses:

  • For j = 0 (the first element is 1):
    • s1 = s2 = 1. No window adjustment needed since neither s1 nor s2 is over the goal yet.
  • For j = 1 (the second element is 0):
    • s1 = s2 = 1. Still no adjustment as we are not over the goal.
  • For j = 2 (the third element is 1):
    • s1 = s2 = 2. Since s2 >= goal, we increment i2. Now, i2 = 1 and s2 = 1 (s1 remains 2 because we have to exceed goal to adjust i1).
    • i2 - i1 = 1. We found one valid subarray [1, 0, 1] and increment ans by 1.
  • For j = 3 (the fourth element is 0):
    • s1 = 2 and s2 = 1. No adjustment required.
  • For j = 4 (the fifth element is 1):
    • s1 = s2 = 2. Both sums are equal to the goal.
    • Since s1 == goal, we increment i1. Now, i1 = 1 and s1 = 1.
    • Similarly, i2 also increments because s2 >= goal. Now, i2 = 3 and s2 = 0.
    • i2 - i1 = 2. The two new valid subarrays are [1, 0, 1] and [0, 1] ending at j=4. So we increment ans 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How does quick sort divide the problem into subproblems?


Recommended Readings