Topics › Sliding Window and Two Pointers › Medium Problems

Binary Subarrays With Sum

Hard TUF ID 923 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given a binary array nums (each element is 0 or 1) and an integer goal. Return the number of non-empty subarrays (contiguous blocks) whose elements sum to exactly goal.

Constraints: 1 ≤ n ≤ 3 × 10^4, 0 ≤ goal ≤ n. The answer is at most n(n + 1) / 2 ≈ 4.5 × 10^8, which fits in an int.

Example 1

nums = [1, 0, 1, 0, 1], goal = 2
answer = 4          // [1,0,1] at 0..2, [1,0,1,0] at 0..3, [0,1,0,1] at 1..4, [1,0,1] at 2..4

Example 2

nums = [0, 0, 0, 0, 0], goal = 0
answer = 15         // every one of the 5 * 6 / 2 subarrays has sum 0

Approach 1: Brute force

Intuition. Enumerate every subarray by its start i and end j, keeping a running sum so that each extension costs O(1). Because all elements are non-negative, the running sum never decreases as j moves right; once it exceeds goal, no later end can bring it back, so we break.

Algorithm.

1. For each i: sum = 0.
2. For j = i ..: add nums[j]. If sum == goal, count it; if sum > goal, break.
3. Return the count.

static int bruteForce(int[] nums, int goal) {
    int n = nums.length, count = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == goal) count++;
            else if (sum > goal) break;            // sums only grow: nothing further from i can match
        }
    }
    return count;
}

Complexity. Time O(n^2) in the worst case (for example all zeros with goal = 0). Space O(1).

Approach 2: Better, prefix sums and a hash map

Intuition. Let P[t] be the sum of the first t elements, with P[0] = 0. The subarray nums[i..j] has sum P[j + 1] - P[i]. It equals goal exactly when P[i] = P[j + 1] - goal. So while scanning, for each new prefix we ask: how many earlier prefixes equal prefix - goal? A map from prefix value to how often it occurred answers that in O(1).

The map must start with {0: 1} to represent the empty prefix; otherwise subarrays that start at index 0 are missed.

Algorithm.

1. freq = {0: 1}, prefix = 0, count = 0.
2. For each x: prefix += x; add freq[prefix - goal] to count; increment freq[prefix].
3. Return count.

static int better(int[] nums, int goal) {
    Map<Integer, Integer> freq = new HashMap<>();
    freq.put(0, 1);                                // the empty prefix
    int prefix = 0, count = 0;
    for (int x : nums) {
        prefix += x;
        count += freq.getOrDefault(prefix - goal, 0);
        freq.merge(prefix, 1, Integer::sum);
    }
    return count;
}

Complexity. Time O(n) with average O(1) map operations. Space O(n) for the map. (Since prefixes here lie in 0..n, an int[n + 1] array works too.)

This method works for any integers, including negatives. The next approach uses the fact that our values are non-negative to drop the extra space.

Approach 3: Optimal, “at most” minus “at most”

Intuition. Sliding windows are great at answering “at most” questions but awkward with “exactly”. With zeros in the array, a window with sum exactly goal can be stretched or shrunk over zeros without changing its sum, so there is no single natural window per end point. The fix is a counting identity:

number of subarrays with sum exactly goal = (number with sum at most goal) − (number with sum at most goal − 1).

Each subarray with sum ≤ goal either has sum exactly goal or sum ≤ goal − 1, so the subtraction leaves exactly what we want.

Counting subarrays with sum at most g is a clean sliding window because the elements are non-negative: shrinking a window never increases its sum. For each right end r, move l right until the window sum is at most g. Then every start between l and r gives a valid subarray ending at r (they are sub-windows of a valid window), which is r - l + 1 subarrays. Summing that over all r counts each valid subarray exactly once, by its right end.

Algorithm.

1. atMost(g): if g < 0 return 0. Otherwise run the window, adding r - l + 1 for every r.
2. Return atMost(goal) - atMost(goal - 1).

static int optimal(int[] nums, int goal) {
    return atMost(nums, goal) - atMost(nums, goal - 1);
}

static int atMost(int[] nums, int goal) {
    if (goal < 0) return 0;                        // no subarray of a 0/1 array has a negative sum
    int l = 0, sum = 0, count = 0;
    for (int r = 0; r < nums.length; r++) {
        sum += nums[r];
        while (sum > goal) {
            sum -= nums[l];
            l++;
        }
        count += r - l + 1;                        // every start in [l, r] gives a valid subarray ending at r
    }
    return count;
}

Dry run of atMost(nums, 2) and atMost(nums, 1) on nums = [1, 0, 1, 0, 1]:

14 − 10 = 4, matching the expected answer.

Complexity. Time O(n): two window passes, each moving l and r at most n times. Space O(1).

Edge cases and pitfalls

• goal = 0. atMost(goal - 1) becomes atMost(-1). Without the goal < 0 guard, while (sum > -1) would keep moving l past r and read out of bounds. The guard returns 0, which is correct because no sum is negative.
• All zeros. [0,0,0,0,0] with goal = 0 counts all 15 subarrays. The brute force never breaks here, which is its worst case.
• Goal above the total. [1,0,1] with goal = 5 gives 0; both “at most” counts equal the total number of subarrays and cancel.
• Missing the empty prefix. In Approach 2, forgetting freq.put(0, 1) drops every subarray that starts at index 0.
• Negative numbers. The sliding-window approach depends on non-negative elements. For general integers use the prefix-sum map.

Related problems

• Count number of Nice subarrays is this exact problem after mapping each number to number % 2.
• Count subarrays with given sum is the general-integer version, solved with the prefix-sum map.
• Subarrays with K Different Integers uses the same “exactly = at most − at most” identity on distinct counts.
• Count subarrays with given xor K applies the prefix-map trick to XOR.