Binary Subarrays with sum

Problem Link

930. Binary Subarrays With Sum – LeetCode

Problem Statement

Given a binary array nums (containing only 0s and 1s) and an integer goal, return the number of non-empty subarrays whose sum is equal to goal.

A subarray is a contiguous portion of the array.

Examples

Example 1:

Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation: The subarrays are:
- [1,0,1]
- [0,1,0,1]
- [1,0,1] (starting from index 2)
- [1,0,1] (starting from index 1)

Example 2:

Input: nums = [0,0,0,0,0], goal = 0
Output: 15
Explanation:
All subarrays with 0s have sum = 0.
- There are 5 individual zeros → 5
- 4 subarrays of 2 zeros → 4
- 3 subarrays of 3 zeros → 3
- 2 subarrays of 4 zeros → 2
- 1 subarray of 5 zeros → 1
→ Total = 5 + 4 + 3 + 2 + 1 = 15

Constraints

• 1 <= nums.length <= 3 * 10⁴

• nums[i] is either 0 or 1

• 0 <= goal <= nums.length

Intuition

To count subarrays with exact sum = goal, we can compute:

count of subarrays with sum <= goal - count of subarrays with sum <= goal - 1

This technique converts the problem into two "at most sum" subarray problems — which can be efficiently solved using a sliding window.

Approach: Sliding Window with At Most K Sum

Key Insight:

• For binary arrays, subarray sum is equivalent to the number of 1s.

• So, we can use a sliding window to count how many subarrays have sum ≤ goal.

• Then subtract the count of subarrays with sum ≤ goal - 1 to get the exact sum = goal.

Java Code

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        return slidingWindow(nums, goal) - slidingWindow(nums, goal - 1);
    }

    public int slidingWindow(int[] nums, int goal) {
        if (goal < 0) return 0;

        int s = 0, currSum = 0, cnt = 0;

        for (int e = 0; e < nums.length; e++) {
            currSum += nums[e];

            while (s <= e && currSum > goal) {
                currSum -= nums[s++];
            }

            cnt += e - s + 1;
        }

        return cnt;
    }
}

Time and Space Complexity

Dry Run

Input:

nums = [1,0,1,0,1], goal = 2

Step 1: Count subarrays with sum ≤ 2

→ slidingWindow(nums, 2) → returns 10

Step 2: Count subarrays with sum ≤ 1

→ slidingWindow(nums, 1) → returns 6

Result:

→ 10 - 6 = 4

Correct!

Follow-up: Why This Works?

The trick of:

exact = atMost(goal) - atMost(goal - 1)

works only for non-negative arrays, like binary arrays. Because:

• Every time you add a new element, the sum increases or stays same.

• So we can safely shrink the window when the sum exceeds goal.

Alternate Approaches

• Prefix Sum + HashMap (using count of prefix sums):

  • Time: O(n), Space: O(n)

  • More generic but less intuitive for binary arrays

Conclusion

This problem showcases a clever twist on the sliding window technique:

• Transform exact sum into two "at most" problems

• Efficiently solve using two pointers

This pattern generalizes well to similar problems involving subarrays with a specific sum — especially when dealing with non-negative arrays.