Binary Subarray With Sum - Sliding Window - Visualization

You are given a binary array nums (containing only 0s and 1s), and an integer goal.

Your task is to count the number of non-empty subarrays such that the sum of elements in the subarray is exactly equal to goal.

Example:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4

Explanation: The subarrays with sum 2 are:
[1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1]

Understanding the Problem

We are given a binary array nums, meaning it only contains 0s and 1s. Along with this array, we are given a target value goal. Our task is to count how many contiguous subarrays (non-empty) have a sum that is exactly equal to goal.

For example:

Input: nums = [1, 0, 1, 0, 1], goal = 2  
Output: 4

Here, the subarrays that sum to 2 are:

• [1, 0, 1]
• [1, 0, 1, 0]
• [0, 1, 0, 1]
• [1, 0, 1] (again, starting from a later index)

This problem might remind us of brute-force approaches, but for performance, we aim to use the Sliding Window technique. Let's break it down step-by-step in a way that’s easy to follow for beginners.

Step-by-Step Solution with Example

Step 1: Think about the meaning of subarray sums

A subarray is a contiguous part of the array. So to get the sum of a subarray, we can add all its elements. But instead of checking every possible subarray (which is slow), we look for a smarter way using prefix logic and window-based counting.

Step 2: Use the idea of “at most”

Let’s define a helper function atMost(k) which gives us the number of subarrays whose sum is at most k. Why? Because the number of subarrays whose sum is exactly equal to goal is:

atMost(goal) - atMost(goal - 1)

This trick helps us isolate the exact count we care about!

Step 3: Sliding Window for atMost(k)

Here’s the idea: we'll maintain a window from left to right and move right forward step-by-step. At every step, we’ll check if the sum of the window is still within our goal.

• If yes, then every subarray that ends at right and starts from left to right is valid → there are (right - left + 1) such subarrays.
• If the sum exceeds the goal, we move left forward and subtract from the sum.

Step 4: Walkthrough with the Example

Let’s go step by step with nums = [1, 0, 1, 0, 1] and goal = 2.

We compute:

count(atMost(2)) → counts all subarrays with sum ≤ 2  
count(atMost(1)) → counts all subarrays with sum ≤ 1  
count(goal) = atMost(2) - atMost(1)

This difference gives us the exact number of subarrays with sum == 2!

Step 5: Code for atMost

function atMost(nums, goal) {
  let left = 0, sum = 0, count = 0;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum > goal) {
      sum -= nums[left++];
    }
    count += (right - left + 1);
  }
  return count;
}

function numSubarraysWithSum(nums, goal) {
  return atMost(nums, goal) - atMost(nums, goal - 1);
}

Edge Cases

• Empty array: Should return 0 since there are no subarrays.
• All zeroes: If goal is 0, we must count all continuous segments of zeroes.
• Goal greater than total sum: No subarrays will match, so return 0.
• Single element arrays: If the single element matches the goal, return 1, else 0.

Our logic naturally handles these because:

• The sliding window shrinks when it exceeds the sum.
• When goal = 0, atMost(-1) returns 0, so atMost(0) - 0 is valid.

Final Thoughts

This problem is a classic use-case for prefix logic and the sliding window. By understanding what "at most k" subarrays mean, we simplify our logic and handle even tricky edge cases easily.

Always look for reusable helper patterns like atMost — they reduce repetition and keep your logic clean and efficient!

1. We define a helper function atMost(goal) that returns the count of subarrays with sum ≤ goal using a sliding window.
2. In this helper function, use two pointers: left and right to define a window, and a variable sum to track the sum of elements in the window.
3. Traverse the array with right from 0 to n-1:
4. → Add nums[right] to sum.
5. → While sum > goal, subtract nums[left] and move left forward.
6. → Add (right - left + 1) to the count (this is the number of valid subarrays ending at right).
7. The final result is: atMost(goal) - atMost(goal - 1), which gives the count of subarrays with exact sum equal to goal.

O(1)

Explanation: The algorithm uses only a constant amount of extra space for counters, pointers, and sum tracking. No additional data structures are required.