What is the brute force approach and complexity for Binary Subarrays With Sum?

Fix each start, grow the end, count when the sum hits goal with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Binary Subarrays With Sum?

Two at-most windows; their difference is the exactly-goal count with optimal time complexity O(N) and space complexity O(1).

How do you identify the pattern for Binary Subarrays With Sum?

Look for key signals in the prompt: "contiguous subarrays" indicates We are counting ranges [l..r] → window or prefix sum.; "count how many" indicates The answer is a count, so each right end adds a number of starts (right − left + 1), not a max.; "sum equals exactly goal" indicates "Exactly" breaks the shrink rule → split into two "at most" counts.; "only 0s and 1s" indicates No negatives, so "sum ≤ k" behaves well for a window. With negatives, only the prefix-sum version works..

Binary Subarrays With Sum

Medium·LeetCode #930Basic Anchor

LeetCode

Jump:

30-Second Mental ModelExactly K = atMost(goal) − atMost(goal − 1)

Complexity:O(N²)→O(N)

Key Insight

Counting subarrays with sum ≤ k is easy with a sliding window. So count sum ≤ goal, count sum ≤ goal − 1, and subtract. What is left is exactly the subarrays with sum goal.

Core Validity Invariant

In each pass, the window is valid when sum ≤ k. Adding elements can only make the sum bigger and removing them can only make it smaller, so this rule is safe to shrink on — unlike "sum = goal".

Problem

You are given an array nums that contains only 0s and 1s, and a number goal.

Count how many contiguous, non-empty subarrays add up to exactly goal.

Input

A binary array nums (every value is 0 or 1) and an integer goal.

Output

The number of non-empty subarrays whose sum equals goal.

Example 1

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

Output: 4

The subarrays with sum 2 are [1,0,1] (indices 0..2), [1,0,1,0] (0..3), [0,1,0,1] (1..4) and [1,0,1] (2..4).

Example 2

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

Output: 15

Every subarray is all zeros, so every one of the 5·6/2 = 15 subarrays has sum 0.

Constraints

• 1 ≤ nums.length ≤ 3 · 10^4
• nums[i] is either 0 or 1
• 0 ≤ goal ≤ nums.length

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I fix where a subarray ends, how many different starts could give the same sum?
2.
What does a 0 do to the sum when it enters or leaves the window?
3.
If my window has sum exactly goal, should I shrink it or not? Can I tell?
4.
Is "sum ≤ goal" easier to keep true with a window than "sum = goal"? Why?
5.
If I can count subarrays with sum ≤ x for any x, how do I get the ones with sum = x?

Brute force approach

Idea

For every start, walk the end to the right while keeping a running sum. Each time the sum equals goal, count one. Since values are 0 or 1, the sum never goes down, so we can stop as soon as it passes goal.

Thinking process

1
A subarray is fixed by its start and its end. Try every pair.
2
Do not re-add the whole subarray each time: for a fixed start, add one more element as the end moves right.
3
First instinct is a sliding window that shrinks when sum > goal and counts when sum = goal. Try it on a small example (see the visual): it misses subarrays, because zeros let several starts share the same sum.
4
So until we find a window rule we can trust, the safe answer is to check every start.

Visual

A window that just shrinks when sum > goal and counts when sum == goal. Orange cells are starts it misses.

Why a direct window failsnums = [1, 0, 0, 1, 0, 1, 1], goal = 2step 1/8

nums

▲L R

Naive window

sum: 1
counted so far: 0
real starts for this R: none

sum 1 ≠ 2

Sum is 1, not 2, so nothing is counted.

Code & Implementation

brute.cpp

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        int n = nums.size();
        int count = 0;

        // Try every start, then grow the end one step at a time.
        for (int start = 0; start < n; start++) {
            int sum = 0;
            for (int end = start; end < n; end++) {
                sum += nums[end];
                if (sum == goal) count++;
                // Numbers are never negative, so the sum can only grow from here.
                if (sum > goal) break;
            }
        }
        return count;
    }
};

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        int n = nums.length;
        int count = 0;

        // Try every start, then grow the end one step at a time.
        for (int start = 0; start < n; start++) {
            int sum = 0;
            for (int end = start; end < n; end++) {
                sum += nums[end];
                if (sum == goal) count++;
                // Numbers are never negative, so the sum can only grow from here.
                if (sum > goal) break;
            }
        }
        return count;
    }
}

class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        n = len(nums)
        count = 0

        # Try every start, then grow the end one step at a time.
        for start in range(n):
            s = 0
            for end in range(start, n):
                s += nums[end]
                if s == goal:
                    count += 1
                if s > goal:
                    break

        return count

export function numSubarraysWithSum(nums: number[], goal: number): number {
    const n = nums.length;
    let count = 0;

    // Try every start, then grow the end one step at a time.
    for (let start = 0; start < n; start++) {
        let sum = 0;
        for (let end = start; end < n; end++) {
            sum += nums[end];
            if (sum === goal) count++;
            if (sum > goal) break;
        }
    }
    return count;
}

Complexity

Time O(N²)Space O(1)

There are about n²/2 (start, end) pairs. With n = 3·10^4 that is around 4.5·10^8 steps in the worst case (for example all zeros and goal = 0) — too slow.

Better approach

Why brute force is slow

For each end, brute force tries every start separately, even when many starts give the same sum.

What repeated work are we doing?

The sum of nums[l..r] is recomputed (by extending) for every start l, when it is really just prefix[r+1] − prefix[l].

What information can we reuse?

Store each prefix sum once in a map with its count. Then all starts that work for this end are counted in one lookup.

New approach

Idea

Let prefix be the sum of everything up to the current index. A subarray (l..r] has sum prefix[r] − prefix[l]. It equals goal when prefix[l] = prefix[r] − goal. So keep a map of how many times each prefix sum has appeared, and at each index add seen[prefix − goal].

Thinking process

1
Brute force asks, for each end, "which starts give sum goal?" and checks them one by one.
2
Any subarray sum is the difference of two running totals. So the question becomes: how many earlier running totals equal prefix − goal?
3
A hash map from running total to how many times we saw it answers that in O(1).
4
This is exactly Subarray Sum Equals K from the Prefix Sum pattern. It works for any integers, so it does not even need the 0/1 fact.

Visual

sum(l..r) = prefix[r] − prefix[l−1], so count earlier prefixes equal to prefix − goal.

Prefix sums + hash mapnums = [1, 0, 0, 1, 0, 1, 1], goal = 2step 1/9

nums

seen (prefix → times)

0:1

State

prefix: 0
need: —
count: 0

Start: the empty prefix has sum 0

Put prefix sum 0 in the map once. It stands for "start the subarray at index 0".

Code & Implementation

better.cpp

class Solution {
public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        // seen[p] = how many prefixes so far have sum p.
        unordered_map<int, int> seen;
        seen[0] = 1;              // the empty prefix, before index 0

        int prefix = 0, count = 0;
        for (int x : nums) {
            prefix += x;
            // A subarray ending here has sum goal exactly when an earlier
            // prefix had sum (prefix - goal). Count all of them at once.
            auto it = seen.find(prefix - goal);
            if (it != seen.end()) count += it->second;
            seen[prefix]++;
        }
        return count;
    }
};

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numSubarraysWithSum(int[] nums, int goal) {
        // seen[p] = how many prefixes so far have sum p.
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1);              // the empty prefix, before index 0

        int prefix = 0, count = 0;
        for (int x : nums) {
            prefix += x;
            // A subarray ending here has sum goal exactly when an earlier
            // prefix had sum (prefix - goal). Count all of them at once.
            count += seen.getOrDefault(prefix - goal, 0);
            seen.put(prefix, seen.getOrDefault(prefix, 0) + 1);
        }
        return count;
    }
}

from collections import defaultdict

class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        seen: dict[int, int] = defaultdict(int)
        seen[0] = 1

        prefix = 0
        count = 0
        for x in nums:
            prefix += x
            count += seen[prefix - goal]
            seen[prefix] += 1

        return count

export function numSubarraysWithSum(nums: number[], goal: number): number {
    const seen = new Map<number, number>();
    seen.set(0, 1);

    let prefix = 0;
    let count = 0;
    for (const x of nums) {
        prefix += x;
        count += seen.get(prefix - goal) || 0;
        seen.set(prefix, (seen.get(prefix) || 0) + 1);
    }
    return count;
}

Complexity

Time O(N)Space O(N)

Fast enough. The cost is the map, which can hold up to n + 1 different prefix sums. Because this array only has 0s and 1s, a window can do the same job with O(1) extra space.

Optimized approach

Idea

Counting subarrays with sum ≤ k is easy with a sliding window. So count sum ≤ goal, count sum ≤ goal − 1, and subtract. What is left is exactly the subarrays with sum goal.

Start from brute force

Brute force fixes a start and walks every end. A first try at a window — shrink when sum > goal, count when sum = goal — is faster but wrong: it counts only one start per end.

Find the repeated work

For a fixed end, all the starts that give sum goal sit next to each other (they differ only by zeros). Brute force checks them one by one. A window could count a whole block of starts at once — but only if its shrink rule is trustworthy, and "exactly goal" is not.

Define the state — what variables do I need?

k: The limit for this pass: `goal` in the first pass, `goal − 1` in the second.
left, right: The current window is nums[left..right]. It is the longest window ending at right whose sum is ≤ k.
sum: Sum of nums[left..right], which is the number of 1s inside.
count: How many subarrays with sum ≤ k we have found so far in this pass.

Define validity

Define the transitions — when does each pointer move, and why is it safe?

Every step

sum += nums[right]

The window grows by one on the right.

sum > k

sum -= nums[left]; left++ (repeat until sum ≤ k)

Any window that starts at the old left and ends here or later is also too big, so that start is useless from now on. Zeros come off without changing the sum; we keep going until a 1 leaves.

After shrinking

count += right − left + 1

[left..right] fits, and every subarray [s..right] with s ≥ left is inside it, so its sum is no bigger. That is right − left + 1 valid subarrays ending at right.

At the end

return atMost(goal) − atMost(goal − 1)

Every subarray with sum ≤ goal − 1 was counted in both passes and cancels out. Only the ones with sum exactly goal are left. atMost(−1) is 0.

What does the current window add to the answer?

In each pass, the right end adds right − left + 1: all subarrays ending at right with sum ≤ k. The final answer is the first pass total minus the second.

Code & Implementation

optimal.cpp

class Solution {
    // Number of subarrays whose sum is at most k.
    int atMost(vector<int>& nums, int k) {
        if (k < 0) return 0;      // no sum of 0s and 1s is negative
        int left = 0, sum = 0, count = 0;
        for (int right = 0; right < (int)nums.size(); right++) {
            sum += nums[right];
            // Too big: drop from the left until the sum fits again.
            while (sum > k) {
                sum -= nums[left];
                left++;
            }
            // Every start from left to right gives a sum <= k.
            count += right - left + 1;
        }
        return count;
    }

public:
    int numSubarraysWithSum(vector<int>& nums, int goal) {
        // (sum <= goal) minus (sum <= goal - 1) leaves exactly (sum == goal).
        return atMost(nums, goal) - atMost(nums, goal - 1);
    }
};

class Solution {
    // Number of subarrays whose sum is at most k.
    private int atMost(int[] nums, int k) {
        if (k < 0) return 0;      // no sum of 0s and 1s is negative
        int left = 0, sum = 0, count = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            // Too big: drop from the left until the sum fits again.
            while (sum > k) {
                sum -= nums[left];
                left++;
            }
            // Every start from left to right gives a sum <= k.
            count += right - left + 1;
        }
        return count;
    }

    public int numSubarraysWithSum(int[] nums, int goal) {
        // (sum <= goal) minus (sum <= goal - 1) leaves exactly (sum == goal).
        return atMost(nums, goal) - atMost(nums, goal - 1);
    }
}

class Solution:
    def numSubarraysWithSum(self, nums: list[int], goal: int) -> int:
        def at_most(k: int) -> int:
            if k < 0:
                return 0
            left = 0
            s = 0
            count = 0
            for right in range(len(nums)):
                s += nums[right]
                while s > k:
                    s -= nums[left]
                    left += 1
                count += right - left + 1
            return count

        return at_most(goal) - at_most(goal - 1)

function atMost(nums: number[], k: number): number {
    if (k < 0) return 0;
    let left = 0;
    let sum = 0;
    let count = 0;
    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum > k) {
            sum -= nums[left];
            left++;
        }
        count += right - left + 1;
    }
    return count;
}

export function numSubarraysWithSum(nums: number[], goal: number): number {
    return atMost(nums, goal) - atMost(nums, goal - 1);
}

Complexity

Time O(N)Space O(1)

Two passes, and in each pass left and right only move forward, so each pass is at most 2n pointer moves.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Fix each start, grow the end, count when the sum hits goal	O(N²)	O(1)
Better	Count earlier prefix sums equal to (current prefix − goal)	O(N)	O(N)
Optimal	Two at-most windows; their difference is the exactly-goal count	O(N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“contiguous subarrays”We are counting ranges [l..r] → window or prefix sum.
“count how many”The answer is a count, so each right end adds a number of starts (right − left + 1), not a max.
“sum equals exactly goal”"Exactly" breaks the shrink rule → split into two "at most" counts.
“only 0s and 1s”No negatives, so "sum ≤ k" behaves well for a window. With negatives, only the prefix-sum version works.

Contiguous range+count+sum exactly goal+non-negative values→Exactly K = atMost(goal) − atMost(goal − 1)

This is the anchor of the Exactly K sub-pattern. You already know how to count "at most" subarrays (the At Most K sub-pattern). Here the rule is "sum ≤ k" on a 0/1 array, and the new move is the subtraction. The same problem is also a classic Prefix Sum + hash map problem (Subarray Sum Equals K). Know both: prefix sums work even with negative numbers; the two-window trick only works when values are non-negative, but uses O(1) space.

Don't make this mistake

Counting with a single "sum == goal" window

✗ while (sum > goal) sum -= nums[left++]; if (sum == goal) count++;

✓ return atMost(goal) - atMost(goal - 1);

For one right end, several starts can give sum goal (they differ only by zeros on the left). This code counts just one of them. On [0,0,1], goal 1, it returns 1 instead of 3.

Forgetting atMost(−1)

✗ int atMost(vector<int>& nums, int k) { int left = 0, sum = 0, count = 0; ...

✓ if (k < 0) return 0;

When goal = 0 you call atMost(−1). Without the guard, while (sum > -1) is always true (a sum is never negative), so left runs past right and then off the end of the array. No subarray has a negative sum, so the answer is 0.

Adding 1 per step instead of right − left + 1

✗ count += 1;

✓ count += right - left + 1;

We count subarrays, not windows. All starts from left to right give a valid subarray ending at right.

Using the window trick when there are negative numbers

This is a pattern-confusion trap. On a general integer array (like Subarray Sum Equals K), "sum ≤ k" is no longer monotonic — adding a negative number makes the sum smaller. There you must use the prefix sum + hash map approach. The two-window trick works here only because values are 0 or 1.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Count Number of Nice Subarrays