Binary Subarrays With Sum (LeetCode 930)
You will see how an exact count that no single window can track becomes the difference of two "at most" counts.
You get an array nums in which every element is 0 or 1, and a whole number goal. A subarray is a run of one or more neighbouring elements of nums, taken without gaps. Count the subarrays whose elements add up to exactly goal, and return that number.
Subarrays are told apart by where they start and end: two runs at different positions both count, even if they hold the same values. When goal is 0, the subarrays made only of zeros are the ones that count.
Worked Examples
nums = [1,0,1,0,1], goal = 24nums = [0,0,0,0,0], goal = 015⚖️Formal Constraints & Bounds
1 <= nums.length <= 3 * 104nums[i]is either0or1.0 <= goal <= nums.length
Why It Works & Core Invariant
"Exactly goal" is not a window you can slide, because zeros join and leave without changing the sum; "at most limit" is, so count at_most(goal) - at_most(goal - 1), where at_most(-1) is 0.
Real-World Scenario & Production Applications
Counting time windows with an exact number of events: a monitoring system that asks how many stretches of a minute-by-minute log contain exactly two failed deploys counts "at most two" and "at most one" with two sliding windows and subtracts, instead of checking every stretch.
Step-by-Step Execution Trace Table
nums = [1,0,0,1,0], goal = 0 (the trap preset): the answer is at_most(0) - at_most(-1).
| Step | Call | right | nums[right] | window after shrinking | left | count += right - left + 1 |
|---|---|---|---|---|---|---|
| 1 | at_most(0) | 0 | 1 | 1 > 0: drop nums[0], window 0 | 1 | + 0 -> 0 |
| 2 | at_most(0) | 1 | 0 | 0 | 1 | + 1 -> 1 |
| 3 | at_most(0) | 2 | 0 | 0 | 1 | + 2 -> 3 |
| 4 | at_most(0) | 3 | 1 | 1 > 0: drop nums[1], nums[2], nums[3], window 0 | 4 | + 0 -> 3 |
| 5 | at_most(0) | 4 | 0 | 0 | 4 | + 1 -> 4 |
| 6 | at_most(-1) | limit < 0: return 0 at once | 0 | |||
| 7 | answer | 4 - 0 = 4 |
Step 3 adds 2: the zero runs [0] (index 2) and [0,0] (indices 1 to 2) both end at right = 2. Without the guard in step 6, at_most(-1) would look for a window with a negative sum, move left past right, and read past the end of nums.
| 1 | "Exactly `goal`" can't be slid, but "at most `limit`" can: count both `at_most(goal)` and `at_most(goal - 1)` and subtract. |
| 2 | Keep this true: inside `at_most(limit)`, `nums[left..right]` is the longest window ending at `right` whose sum is at most `limit`. |
| 3 | The shape: a helper `at_most(limit)` with one `for right` loop that grows the window, an inner loop that shrinks it from the left, and one addition to `count` per `right`; the answer combines two calls of the helper. |
| 4 | The trap: `goal = 0` asks for `at_most(-1)`. Return 0 for a negative `limit`, or the shrink loop walks `left` off the end of `nums`. |
Target: Binary Subarrays With Sum (LeetCode 930). No subarray of 0s and 1s has a negative sum, so `at_most(-1)` is 0; returning early also keeps the window from running off the end when `goal` is 0.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting subarrays whose sum is exactly goal sounds like a sliding window, but it isn't one: in [0,0,1,0,0] with goal = 1, the 1 fits in nine different runs, and the zeros on both sides can join or leave without changing the sum. No single left edge describes them all. Counting subarrays whose sum is at most limit is a clean window: if nums[left..right] fits, every shorter window ending at right fits too, so for each right there is one smallest left, and right - left + 1 subarrays end there. The At-Most Trick counts two of those and subtracts: at_most(goal) - at_most(goal - 1) leaves exactly the sums equal to goal.
🧺 The Analogy: Shelves With a Weight Limit
A shelf holds at most 2 kilos. Knowing how many runs of books fit on a 2-kilo shelf, and how many fit on a 1-kilo shelf, tells you how many runs weigh more than 1 kilo but at most 2: subtract the two numbers. Counting runs that weigh exactly some amount directly is awkward, because weightless bookmarks can be added or removed at either end of a run.
🪄 The Mathematical Harmony / Magic Trick
def at_most(limit): if limit < 0: return 0 # at_most(-1): nothing has a negative sum left = window = count = 0 for right in range(len(nums)): window += nums[right] while window > limit: window -= nums[left] left += 1 count += right - left + 1 # every start from left to right fits return count return at_most(goal) - at_most(goal - 1) Each subarray with sum at most goal has sum exactly goal or at most goal - 1, so the subtraction is exact. When goal is 0, the second call asks for a negative limit: no window can ever fit, so without the early return 0 the while loop would push left past right and off the end of nums.
💡 Summary
Exactly goal = at most goal minus at most goal - 1; each count is one sliding window that adds right - left + 1 per end, and at_most(-1) is 0. time, extra space.
A negative limit:
goal = 0asks forat_most(-1).if limit < 0: return 0, or thewhile window > limitloop walksleftpastrightand off the end ofnums.Counting one subarray per end: add
right - left + 1, not 1. Every start fromlefttorightgives a subarray whose sum is at mostlimit.Shrinking only once: use
while window > limit, notif. After a 1 joins,nums[left]may be a 0, and one step leaves the sum overlimit.One window for "exactly": counting a window when its sum equals
goalmisses the runs that start at a zero the window already dropped; in[1,0,1,0,1]withgoal = 2it finds fewer than 4.Keys left at zero, as in Subarrays with K Different Integers (LC 992): with different values as the amount,
dela value whose count drops to 0, orlen(copies)stays too high.Not the only correct shape: a single window with two left pointers (one marking where it first reaches exactly
kdifferent values, one where it first exceedsk) also solves this in one pass; the at-most/at-most difference is preferred here because it reuses one window function instead of tracking two left edges.
4-Phase Thought Process Model
You will see how a senior engineer hears "count subarrays with exactly goal" and turns it into two "at most" windows.
Pattern Recognition Signals
The 10-second spot
"Count the subarrays whose elements add up to exactly goal" with "every element is 0 or 1": an exact count over subarrays, where adding an element never lowers the sum. "Exactly" can't be slid, but "at most" can, so the signal is the At-Most Trick: exactly(goal) = at_most(goal) - at_most(goal - 1). "When goal is 0" warns that at_most(-1) will be asked for.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Inside at_most(limit), after each right, nums[left..right] is the longest window ending at right whose sum is at most limit, so count += right - left + 1 adds every such subarray once; the answer is at_most(goal) - at_most(goal - 1).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
goal = 0makesat_most(goal - 1)intoat_most(-1):if limit < 0: return 0, orwhile window > limitwalksleftpastrightand off the end ofnums.count += right - left + 1, notcount += 1: in[0,0,0,0,0]withgoal = 0each new zero ends several all-zero runs at once.while window > limit, notif: after a 1 joins,nums[left]may be a 0, and one step leaves the sum overlimit.One window for "exactly" misses subarrays: in
[1,0,1,0,1]withgoal = 2, the run0,1,0,1starts at a 0 that such a window has already dropped.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the At-Most Trick. Counting subarrays whose sum is exactly goal with one window doesn't work, because zeros can join or leave without changing the sum, so there's no single left edge to track. Counting subarrays whose sum is at most some limit does work: I grow the window to the right, shrink it from the left while the sum is over the limit, and add right minus left plus one for every right end, since every start inside the window fits. Then exactly goal is at most goal minus at most goal minus one, because each subarray lands in exactly one of those two groups. The trap is goal equal to zero: that asks for at most minus one, which has to be zero, so I return early for a negative limit instead of letting the window run off the end. Two passes,
O(N)time andO(1)space.
So: exactly = at most goal minus at most goal - 1; each count adds right - left + 1 per end; at_most(-1) is 0.
Complexity & Mathematical Proof
O(N)
at_most(limit) runs for right in range(len(nums)): N steps, each with one addition and one count +=. The inner while window > limit moves left one place per step, and left only moves forward and never passes N, so across the whole pass the while body runs at most N times in all. One pass is O(N). num_subarrays_with_sum makes two passes, at_most(goal) and at_most(goal - 1) (the second returns at once when goal is 0): O(2N) = O(N).
O(1)
Each pass keeps limit, left, window, count and right: O(1) extra space. The two calls run one after the other, so the stack never holds more than one at_most frame. The answer is one integer.
T(N) = 2 passes x (N moves of right + at most N moves of left) = O(N)
at_most(limit) runs for right in range(len(nums)): N steps, each with one addition and one count +=. The inner while window > limit moves left one place per step, and left only moves forward and never passes N, so across the whole pass the while body runs at most N times in all. One pass is O(N). num_subarrays_with_sum makes two passes, at_most(goal) and at_most(goal - 1) (the second returns at once when goal is 0): O(2N) = O(N).
Derivation Progression
N
for right in range(len(nums)) adds each element to window once per pass.
at most N
Each run of the while body moves left forward by one; left never moves back and never passes N, so all shrinks in a pass add up to at most N.
N
count += right - left + 1 is one addition per right, however many subarrays it counts.
O(N)
at_most(goal) and at_most(goal - 1) each cost O(N); their difference is one subtraction.
Variable Definitions
Number of elements, len(nums) (at most 3 * 10^4)
Memory Architecture & Bounds
O(1): one at_most frame at a time
O(1): limit, left, window, count, right
O(1): one integer
Boundary Best / Worst Cases
: goal = 0, so the second pass returns at once, but the first still reads every element
: two full passes, with left crossing the whole array in each
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: **"add up to exactly goal"**, **"every element is 0or1"**, "Count the subarrays". An exact count over subarrays whose amount only grows as elements join: At-Most Trick, at_most(goal) - at_most(goal - 1).
Up to elements. Checking every subarray is about additions; two sliding-window passes are about pointer moves. The answer can reach , which still fits a 32-bit integer, but at elements it would not.
goal = 0 asks for at_most(-1), which must be 0 rather than a loop that reads past the end. On a stream, the two counts can run side by side as two windows over the same input, so the log is read once; the same subtraction answers "exactly K events in a window" as long as events only add, never cancel. Counts over long streams outgrow 32 bits quickly: keep them in 64-bit integers.
Core Algorithmic State Invariants
Zeros join and leave without changing the sum, so no single window tracks "exactly `goal`". "At most `limit`" only shrinks from the left, so one pass counts it.
For `goal = 0` the second count is `at_most(-1)`. `if limit < 0: return 0`, or `while window > limit` walks `left` past `right` and off the end of `nums`.
Each pass moves `right` and `left` forward at most `N` times and adds `right - left + 1` per end: O(N) time, O(1) extra space, for both counts together.
Binary Subarrays With Sum (LeetCode 930)
You will see how an exact count that no single window can track becomes the difference of two "at most" counts.
You get an array nums in which every element is 0 or 1, and a whole number goal. A subarray is a run of one or more neighbouring elements of nums, taken without gaps. Count the subarrays whose elements add up to exactly goal, and return that number.
Subarrays are told apart by where they start and end: two runs at different positions both count, even if they hold the same values. When goal is 0, the subarrays made only of zeros are the ones that count.
Worked Examples
nums = [1,0,1,0,1], goal = 24nums = [0,0,0,0,0], goal = 015⚖️Formal Constraints & Bounds
1 <= nums.length <= 3 * 104nums[i]is either0or1.0 <= goal <= nums.length
Why It Works & Core Invariant
"Exactly goal" is not a window you can slide, because zeros join and leave without changing the sum; "at most limit" is, so count at_most(goal) - at_most(goal - 1), where at_most(-1) is 0.
Real-World Scenario & Production Applications
Counting time windows with an exact number of events: a monitoring system that asks how many stretches of a minute-by-minute log contain exactly two failed deploys counts "at most two" and "at most one" with two sliding windows and subtracts, instead of checking every stretch.
Step-by-Step Execution Trace Table
nums = [1,0,0,1,0], goal = 0 (the trap preset): the answer is at_most(0) - at_most(-1).
| Step | Call | right | nums[right] | window after shrinking | left | count += right - left + 1 |
|---|---|---|---|---|---|---|
| 1 | at_most(0) | 0 | 1 | 1 > 0: drop nums[0], window 0 | 1 | + 0 -> 0 |
| 2 | at_most(0) | 1 | 0 | 0 | 1 | + 1 -> 1 |
| 3 | at_most(0) | 2 | 0 | 0 | 1 | + 2 -> 3 |
| 4 | at_most(0) | 3 | 1 | 1 > 0: drop nums[1], nums[2], nums[3], window 0 | 4 | + 0 -> 3 |
| 5 | at_most(0) | 4 | 0 | 0 | 4 | + 1 -> 4 |
| 6 | at_most(-1) | limit < 0: return 0 at once | 0 | |||
| 7 | answer | 4 - 0 = 4 |
Step 3 adds 2: the zero runs [0] (index 2) and [0,0] (indices 1 to 2) both end at right = 2. Without the guard in step 6, at_most(-1) would look for a window with a negative sum, move left past right, and read past the end of nums.
| 1 | "Exactly `goal`" can't be slid, but "at most `limit`" can: count both `at_most(goal)` and `at_most(goal - 1)` and subtract. |
| 2 | Keep this true: inside `at_most(limit)`, `nums[left..right]` is the longest window ending at `right` whose sum is at most `limit`. |
| 3 | The shape: a helper `at_most(limit)` with one `for right` loop that grows the window, an inner loop that shrinks it from the left, and one addition to `count` per `right`; the answer combines two calls of the helper. |
| 4 | The trap: `goal = 0` asks for `at_most(-1)`. Return 0 for a negative `limit`, or the shrink loop walks `left` off the end of `nums`. |
Target: Binary Subarrays With Sum (LeetCode 930). No subarray of 0s and 1s has a negative sum, so `at_most(-1)` is 0; returning early also keeps the window from running off the end when `goal` is 0.
Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.
while (left < right) for converging pointers; while (right < n) with inner window shrink.
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting subarrays whose sum is exactly goal sounds like a sliding window, but it isn't one: in [0,0,1,0,0] with goal = 1, the 1 fits in nine different runs, and the zeros on both sides can join or leave without changing the sum. No single left edge describes them all. Counting subarrays whose sum is at most limit is a clean window: if nums[left..right] fits, every shorter window ending at right fits too, so for each right there is one smallest left, and right - left + 1 subarrays end there. The At-Most Trick counts two of those and subtracts: at_most(goal) - at_most(goal - 1) leaves exactly the sums equal to goal.
🧺 The Analogy: Shelves With a Weight Limit
A shelf holds at most 2 kilos. Knowing how many runs of books fit on a 2-kilo shelf, and how many fit on a 1-kilo shelf, tells you how many runs weigh more than 1 kilo but at most 2: subtract the two numbers. Counting runs that weigh exactly some amount directly is awkward, because weightless bookmarks can be added or removed at either end of a run.
🪄 The Mathematical Harmony / Magic Trick
def at_most(limit): if limit < 0: return 0 # at_most(-1): nothing has a negative sum left = window = count = 0 for right in range(len(nums)): window += nums[right] while window > limit: window -= nums[left] left += 1 count += right - left + 1 # every start from left to right fits return count return at_most(goal) - at_most(goal - 1) Each subarray with sum at most goal has sum exactly goal or at most goal - 1, so the subtraction is exact. When goal is 0, the second call asks for a negative limit: no window can ever fit, so without the early return 0 the while loop would push left past right and off the end of nums.
💡 Summary
Exactly goal = at most goal minus at most goal - 1; each count is one sliding window that adds right - left + 1 per end, and at_most(-1) is 0. time, extra space.
A negative limit:
goal = 0asks forat_most(-1).if limit < 0: return 0, or thewhile window > limitloop walksleftpastrightand off the end ofnums.Counting one subarray per end: add
right - left + 1, not 1. Every start fromlefttorightgives a subarray whose sum is at mostlimit.Shrinking only once: use
while window > limit, notif. After a 1 joins,nums[left]may be a 0, and one step leaves the sum overlimit.One window for "exactly": counting a window when its sum equals
goalmisses the runs that start at a zero the window already dropped; in[1,0,1,0,1]withgoal = 2it finds fewer than 4.Keys left at zero, as in Subarrays with K Different Integers (LC 992): with different values as the amount,
dela value whose count drops to 0, orlen(copies)stays too high.Not the only correct shape: a single window with two left pointers (one marking where it first reaches exactly
kdifferent values, one where it first exceedsk) also solves this in one pass; the at-most/at-most difference is preferred here because it reuses one window function instead of tracking two left edges.
4-Phase Thought Process Model
You will see how a senior engineer hears "count subarrays with exactly goal" and turns it into two "at most" windows.
Pattern Recognition Signals
The 10-second spot
"Count the subarrays whose elements add up to exactly goal" with "every element is 0 or 1": an exact count over subarrays, where adding an element never lowers the sum. "Exactly" can't be slid, but "at most" can, so the signal is the At-Most Trick: exactly(goal) = at_most(goal) - at_most(goal - 1). "When goal is 0" warns that at_most(-1) will be asked for.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Inside at_most(limit), after each right, nums[left..right] is the longest window ending at right whose sum is at most limit, so count += right - left + 1 adds every such subarray once; the answer is at_most(goal) - at_most(goal - 1).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
goal = 0makesat_most(goal - 1)intoat_most(-1):if limit < 0: return 0, orwhile window > limitwalksleftpastrightand off the end ofnums.count += right - left + 1, notcount += 1: in[0,0,0,0,0]withgoal = 0each new zero ends several all-zero runs at once.while window > limit, notif: after a 1 joins,nums[left]may be a 0, and one step leaves the sum overlimit.One window for "exactly" misses subarrays: in
[1,0,1,0,1]withgoal = 2, the run0,1,0,1starts at a 0 that such a window has already dropped.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use the At-Most Trick. Counting subarrays whose sum is exactly goal with one window doesn't work, because zeros can join or leave without changing the sum, so there's no single left edge to track. Counting subarrays whose sum is at most some limit does work: I grow the window to the right, shrink it from the left while the sum is over the limit, and add right minus left plus one for every right end, since every start inside the window fits. Then exactly goal is at most goal minus at most goal minus one, because each subarray lands in exactly one of those two groups. The trap is goal equal to zero: that asks for at most minus one, which has to be zero, so I return early for a negative limit instead of letting the window run off the end. Two passes,
O(N)time andO(1)space.
So: exactly = at most goal minus at most goal - 1; each count adds right - left + 1 per end; at_most(-1) is 0.
Complexity & Mathematical Proof
O(N)
at_most(limit) runs for right in range(len(nums)): N steps, each with one addition and one count +=. The inner while window > limit moves left one place per step, and left only moves forward and never passes N, so across the whole pass the while body runs at most N times in all. One pass is O(N). num_subarrays_with_sum makes two passes, at_most(goal) and at_most(goal - 1) (the second returns at once when goal is 0): O(2N) = O(N).
O(1)
Each pass keeps limit, left, window, count and right: O(1) extra space. The two calls run one after the other, so the stack never holds more than one at_most frame. The answer is one integer.
T(N) = 2 passes x (N moves of right + at most N moves of left) = O(N)
at_most(limit) runs for right in range(len(nums)): N steps, each with one addition and one count +=. The inner while window > limit moves left one place per step, and left only moves forward and never passes N, so across the whole pass the while body runs at most N times in all. One pass is O(N). num_subarrays_with_sum makes two passes, at_most(goal) and at_most(goal - 1) (the second returns at once when goal is 0): O(2N) = O(N).
Derivation Progression
N
for right in range(len(nums)) adds each element to window once per pass.
at most N
Each run of the while body moves left forward by one; left never moves back and never passes N, so all shrinks in a pass add up to at most N.
N
count += right - left + 1 is one addition per right, however many subarrays it counts.
O(N)
at_most(goal) and at_most(goal - 1) each cost O(N); their difference is one subtraction.
Variable Definitions
Number of elements, len(nums) (at most 3 * 10^4)
Memory Architecture & Bounds
O(1): one at_most frame at a time
O(1): limit, left, window, count, right
O(1): one integer
Boundary Best / Worst Cases
: goal = 0, so the second pass returns at once, but the first still reads every element
: two full passes, with left crossing the whole array in each
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: **"add up to exactly goal"**, **"every element is 0or1"**, "Count the subarrays". An exact count over subarrays whose amount only grows as elements join: At-Most Trick, at_most(goal) - at_most(goal - 1).
Up to elements. Checking every subarray is about additions; two sliding-window passes are about pointer moves. The answer can reach , which still fits a 32-bit integer, but at elements it would not.
goal = 0 asks for at_most(-1), which must be 0 rather than a loop that reads past the end. On a stream, the two counts can run side by side as two windows over the same input, so the log is read once; the same subtraction answers "exactly K events in a window" as long as events only add, never cancel. Counts over long streams outgrow 32 bits quickly: keep them in 64-bit integers.
Core Algorithmic State Invariants
Zeros join and leave without changing the sum, so no single window tracks "exactly `goal`". "At most `limit`" only shrinks from the left, so one pass counts it.
For `goal = 0` the second count is `at_most(-1)`. `if limit < 0: return 0`, or `while window > limit` walks `left` past `right` and off the end of `nums`.
Each pass moves `right` and `left` forward at most `N` times and adds `right - left + 1` per end: O(N) time, O(1) extra space, for both counts together.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| "At most" for a negative limit is empty (the trap) | if limit < 0:
return 0 | No subarray of 0s and 1s has a negative sum, so `at_most(-1)` is 0; returning early also keeps the window from running off the end when `goal` is 0. |
| Grow the window by one element | window += nums[right] | `right` moves once per step, and the window's sum takes in the new element. |
| Shrink from the left until the window fits | while window > limit: | The values are never negative, so dropping elements from the left can only lower the sum; a `while` keeps dropping until it is at most `limit`. |
| Drop the leftmost element | window -= nums[left]
left += 1 | `left` only moves forward, so across a pass it moves at most N times. |
| Count every start that fits | count += right - left + 1 | Every window from `left..right` down to `right..right` has a sum at most `limit`, so one addition counts them all. |
| Exactly = at most minus at most one less | return at_most(goal) - at_most(goal - 1) | A subarray with sum at most `goal` has sum `goal` or at most `goal - 1`, never both, so the difference counts the sums equal to `goal`. |