Binary Subarray With Sum - Sliding Window - Visualization - Visualization

Sliding Window & Two Pointer Problems

Contents

ProblemExamplesSolutionAlgorithmCodeTimeSpace

Problem Statement❯

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]

Examples❯

nums goal Output Description
[1,0,1,0,1] 2 4 Normal case; valid subarrays are [1,0,1], [1,0,1,0], [0,1,0,1], and [1,0,1]
[0,0,0,0,0] 0 15 All possible non-empty subarrays of zeros have sum 0; total count is 5 + 4 + 3 + 2 + 1 = 15
[1,1,1,1] 3 2 Subarrays with sum 3: [1,1,1] (two such subarrays)
[1] 1 1 Single element equal to goal; only one valid subarray [1]
[1] 0 0 Single 1 cannot form sum 0; no valid subarrays
[] 0 0 Empty array; no subarrays possible
[0] 0 1 Single 0 forms a valid subarray with sum 0
[1,1,1] 0 0 No subarray of 1s can sum to 0
[0,1,0,1,0] 1 8 Several combinations of [0,1], [1], [1,0], etc., with sum exactly 1
[1,0,1] 5 0 Sum 5 not possible in any subarray; output is 0

Solution❯

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!

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int atMost(int* nums, int numsSize, int goal) {
    int left = 0, count = 0, sum = 0;
    for (int right = 0; right < numsSize; right++) {
        sum += nums[right];
        while (sum > goal) {
            sum -= nums[left++];
        }
        count += right - left + 1;
    }
    return count;
}

int numSubarraysWithSum(int* nums, int numsSize, int goal) {
    return atMost(nums, numsSize, goal) - atMost(nums, numsSize, goal - 1);
}

int main() {
    int nums[] = {1,0,1,0,1};
    int goal = 2;
    int size = sizeof(nums) / sizeof(nums[0]);
    int result = numSubarraysWithSum(nums, size, goal);
    printf("%d\n", result); // Output: 4
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, the algorithm must traverse the entire array once in the helper function to compute the subarrays with sum ≤ goal and again for goal - 1. Each element is processed in amortized constant time due to the sliding window, resulting in linear time.
Average CaseO(n)On average, each element is added and removed from the sliding window at most once for both helper function calls, leading to a total linear time complexity.
Worst CaseO(n)Even in the worst case, the two-pointer sliding window ensures that each element is visited at most twice — once by the right pointer and once by the left — for both calls to the helper function. Hence, time complexity remains O(n).

Space Complexity❯

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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...