Scale Engineer

Binary Subarrays With Sum

Med
#0884Time: 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.
Patterns
Sliding WindowPrefix Sum
Data structures
ArrayHash Table

Prompt

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 * 104
  • nums[i] is either 0 or 1.
  • 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 count to 0.
  • Use a nested loop structure. The outer loop with index i iterates from 0 to n-1 to select the starting element of the subarray.
  • The inner loop with index j iterates from i to n-1 to select the ending element of the subarray.
  • For each subarray starting at i, maintain a currentSum.
  • In the inner loop, add nums[j] to currentSum.
  • If currentSum equals goal, increment the count.
  • Since all numbers are non-negative, if currentSum exceeds goal, 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.

Solutions

/** * @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 ; };

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

← Previous

Previous problem

Next →

Next problem