Binary Subarrays With Sum — LC 930 Two Sliding Windows in O(n)

Problem Statement#

Given a binary array nums and integer goal, count non-empty subarrays whose sum equals goal.

Constraints:

• 1 less than or equal to nums.length less than or equal to 3 times 10 to the 4
• nums[i] is 0 or 1
• 0 less than or equal to goal less than or equal to nums.length

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

Input:  nums = [0, 0, 0, 0, 0], goal = 0
Output: 15

Why This Problem Matters#

LeetCode 930 — Binary Subarrays With Sum is a Google, Amazon, and Meta interview staple because it isolates the "exactly equal" sliding window trick on the simplest possible inputs: 0s and 1s. Once you can articulate that exactly-goal equals atMost(goal) minus atMost(goal - 1), the same template generalizes to LC 1248 (Count Number of Nice Subarrays) and LC 992 (Subarrays with K Different Integers).

The all-zeros edge case (goal = 0) is the trickiest part. Many candidates write a working solution but lose points on nums = [0, 0, 0] because they double-count windows. Interviewers specifically watch for this.

In production, this pattern surfaces in click-stream analysis ("how many sessions had exactly N clicks?") and in security alerting ("how many windows contain exactly N login failures?").

The Core Insight#

A direct sliding window for "sum equals goal" fails because the constraint is two-sided: tightening one side may violate the other. Instead, use the standard decomposition:

exactly(goal) equals atMost(goal) minus atMost(goal minus 1).

atMost(k) is monotonic and one-sided — shrink while sum is greater than k. Inside atMost, every valid window contributes right - left + 1 subarrays ending at right.

The alternative is a prefix-sum hash map: for each prefix sum S[i], count earlier indices where S[j] = S[i] - goal. That is also O(n) but uses O(n) extra space. The dual sliding window is equally fast at O(1) space, which is why it is the preferred answer in interviews when memory is constrained.

Visual Dry Run#

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

atMost(2) is 14, atMost(1) is 10, answer 14 minus 10 equals 4.

Solution (Optimal)#

class Solution:
    def numSubarraysWithSum(self, nums, goal):
        def at_most(limit):
            if limit < 0:
                return 0
            left, current, total = 0, 0, 0
            for right, value in enumerate(nums):
                current += value
                while current > limit:
                    current -= nums[left]
                    left += 1
                total += right - left + 1
            return total
        return at_most(goal) - at_most(goal - 1)

var numSubarraysWithSum = function(nums, goal) {
    const atMost = (limit) => {
        if (limit < 0) return 0;
        let left = 0, current = 0, total = 0;
        for (let right = 0; right < nums.length; right++) {
            current += nums[right];
            while (current > limit) {
                current -= nums[left];
                left++;
            }
            total += right - left + 1;
        }
        return total;
    };
    return atMost(goal) - atMost(goal - 1);
};

Time: O(n) — two linear passes. Space: O(1) — counters only.

Common Mistakes#

• Forgetting atMost(-1) returns 0. Without the guard the helper enters an infinite loop on goal = 0.
• Trying to slide directly for "sum equals goal" — the constraint is non-monotonic, so the window collapses.
• Counting each valid window as 1 instead of right - left + 1.
• Resetting left between calls if you share state. Each atMost call must be self-contained.
• For all-zeros input, returning the count of single-element subarrays only.

Interview Tips#

• State the decomposition early: "I will compute atMost(goal) minus atMost(goal minus 1)."
• Mention the prefix-sum alternative for breadth.
• Walk through goal = 0 carefully — interviewers love this trap.
• Discuss space tradeoffs: dual sliding is O(1) versus prefix-sum hash O(n).
• Note that this is the binary specialization of LC 992 and LC 1248.

Follow-up Questions#

• Solve using prefix sums and a hash map. Constant time per index, O(n) space.
• What if values can be negative? Sliding window breaks; only prefix-sum hash works.
• Count subarrays with sum at most goal. Single sliding window pass.
• Return one such subarray. Track an example window during atMost(goal).
• Stream version: process nums in chunks. Prefix-sum hash naturally streams.

Key Takeaways#

• LeetCode 930 — Binary Subarrays With Sum solves in O(n) time and O(1) space.
• exactly(goal) equals atMost(goal) minus atMost(goal minus 1) is the universal exact-count trick.
• Sliding window directly on "equals goal" fails because the constraint is two-sided.
• All-zeros input is the killer edge case — handle goal = 0 carefully.
• The prefix-sum hash map alternative trades O(n) space for cleaner code.
• Asked at Google, Amazon, Meta, and Microsoft in array and sliding window rounds.
• Same template applies to LC 1248 (Count Nice Subarrays) and LC 992 (K Different Integers).