Binary Subarrays With Sum | Leetcode 930 | Optimal Prefix/Sliding Window Trick

The problem “Binary Subarrays With Sum” asks to count the number of contiguous subarrays in a binary array nums whose sum equals a given goal. Because the array is binary (only 0s and 1s), we can exploit special properties to achieve an O(n) solution using a clever at-most trick.

Here’s the [Problem Link] to begin with.

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

Brute Force (Enumerate All Starts)

Intuition and Approach

• For each start index i, expand the end index j, maintain a running total.
• If total > goal, break early (since adding more 0/1 can only increase or keep the same).
• If total == goal, increment the count.

Code

class Solution:
    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        count = 0
        n = len(nums)
        for i in range(n):
            total = 0
            for j in range(i, n):
                total += nums[j]
                if total > goal:
                    break
                if total == goal:
                    count += 1
        return count

Why It Works

• Sums in a binary array are non-decreasing as the window expands, enabling an early break once total > goal.

Time and Space Complexity

• Time: O(n^2) in worst case
• Space: O(1)

Optimal (At-Most Trick with Sliding Window / Two Pointers)

Core Insight

For binary arrays, the count of subarrays with sum exactly goal equals:

• count( sum ≤ goal ) − count( sum ≤ goal−1 )

This works because with only 0s and 1s, as goal increases, every new valid subarray adds to the count monotonically. So, we can compute a helper that returns number of subarrays with sum at most X, then subtract.

Helper: Count subarrays with sum ≤ goal

• Maintain a window [left..right] and running Sum.
• Expand right, add nums[right].
• While Sum > goal, shrink from left, subtracting nums[left].
• At each step, all subarrays ending at right and starting from any index in [left..right] are valid, contributing (right - left + 1) to the count.

Code

class Solution:
    def countSubArrayLessThanOrEqualToGoal(self, nums, goal):
        if goal < 0:
            return 0
        count = 0
        n = len(nums)
        left = 0
        right = 0
        Sum = 0
        while right < n:
            Sum += nums[right]
            while Sum > goal:
                Sum -= nums[left]
                left += 1
            count = count + ((right - left) + 1)
            right += 1
        return count

    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
        return self.countSubArrayLessThanOrEqualToGoal(
            nums, goal
        ) - self.countSubArrayLessThanOrEqualToGoal(nums, goal - 1)

Why This Is Correct

• In a binary array, the number of subarrays with sum at most goal can be counted with a single-pass sliding window because as the window grows, the sum increases by at most 1 per step.
• Therefore, exactly-goal counts are obtained by subtracting at-most-goal-1 from at-most-goal.

Edge Cases

• When goal < 0, there are no valid subarrays, so the helper returns 0 (already handled).
• Handles goal = 0 naturally: at-most-0 counts all-zero windows; at-most-(-1) is 0; difference yields exact 0-sum subarrays.

Time and Space Complexity

• Time: O(n) – each pointer moves at most n steps
• Space: O(1)

Alternative Note: Prefix Sum + Hash Map

Another common exact-count method uses a prefix sum and a frequency map:

• For each index, compute running sum pref.
• Subarrays with sum goal ending at current index equal the count of pref - goal seen so far.
• Update map with current pref.
• This also yields O(n) time and O(n) space.

However, the provided solution uses the elegant at-most trick tailored for binary arrays, achieving O(n) time and O(1) space.

Final Takeaway

• Use Brute Force for small inputs to build intuition.
• For production, prefer the at-most sliding window trick:
  exact = atMost(goal) − atMost(goal−1), which is both clean and linear-time for binary arrays.
• Remember this pattern for other “exact sum” problems on binary arrays – it’s a powerful and reusable technique.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.