STEP 10 · SLIDING WINDOW · ATMOST(K) − ATMOST(K−1) · MEDIUM

Binary Subarrays With Sum

WHAT IT SAYS

Given a binary array and a goal, count how many subarrays sum to exactly the goal.

WHAT IT'S REALLY ASKING

"A window can't chase an exact sum — the zeros make it ambiguous, since you can keep sliding and the sum doesn't budge. But a window can absolutely chase 'sum ≤ goal', because that condition only breaks in one direction. So: can you build 'exactly' out of two things you can actually slide?"

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Every start, every end

O(n²) time, O(1) space

Fix a start i, walk right with a running sum, and tick the counter every time the sum lands on the goal. Restart from i + 1. Correct by construction — every subarray gets its sum computed exactly once.

WHERE THE WORK IS WASTED — For a fixed start, the running sum only climbs, so once it passes the goal every further step of that inner loop is guaranteed useless — yet you keep walking to the end of the array. And when you restart at i + 1, you rebuild the sum of s[i+1..r] from zero, even though the previous pass already computed it (it's just the old sum minus one element). Worse, you're re-answering a question with a shape you never exploit: for each end r, the valid starts form a contiguous block, and brute force rediscovers that block from scratch for every single r.

Prefix sums and a tally of what you've seen

O(n) time, O(n) space

Let P[r] be the sum of everything up to r. A subarray ending at r hits the goal exactly when some earlier prefix equals P[r] − goal, so keep a running map of prefix values you've already passed and add its count at each step. This is fast, general, and completely ignores the fact that the array is binary — it works just as well with negative numbers.

KEY OBSERVATION — THE UNLOCKlink

'Exactly' won't slide. 'At most' will. So subtract.

Why the obvious window fails: the sum of a window is a lousy thing to steer toward equality, because zeros let you widen the window without changing the sum at all. When the sum hits the goal you can't tick the counter once and move on — several starts may be sitting on that same sum — and you can't decide whether to move left or right, since both leave the sum untouched. Equality is not a hereditary property; you can't shrink your way back into it reliably. But 'sum ≤ goal' is. Entries are non-negative, so pushing the right edge out can only raise the sum, and pulling the left edge in can only lower it. That gives you the whole machine: a start that's already over the goal is over it forever (the sum never falls as r grows), so the left edge never rewinds — and every start between the left edge and r is also under the goal, so the count of qualifying subarrays ending at r is just the window's width. Call the total atMost(k). Now the bridge. Sums here are integers, so the subarrays with sum ≤ goal split cleanly into those with sum ≤ goal − 1 and those with sum exactly goal — no overlap, nothing left over. Subtract, and the exact count falls out of two slideable quantities: exactly(goal) = atMost(goal) − atMost(goal − 1).

Run the same window twice

O(n) time, O(1) space

Write one routine that counts subarrays with sum ≤ k: advance the right edge, and while the running sum exceeds k, advance the left edge and subtract; then add (r − left + 1) to the count, because every start in the current window is valid. Call it once with goal and once with goal − 1 and return the difference (guard goal = 0, where atMost(−1) is simply 0).

Fuse the subtraction: two left edges, one pass

O(n) time, O(1) space, single pass

The two runs differ only in where their left edge ends up, so track both at once: `lo` is the leftmost start whose sum is still ≤ goal, and `hi` is the leftmost start whose sum has dropped strictly below goal. Every start from lo up to hi − 1 lands on the goal exactly, so add hi − lo at each step. That gap is precisely the run of zeros in front of the window's first 1 — you can literally see the ambiguity that broke the naive window now being counted instead of fought.

WHAT YOU TRADED — The prefix-sum map buys generality — it survives negative numbers — and pays O(n) memory for it; the window drops to O(1) memory but only because non-negativity makes the sum monotone in the window's width, and it dies the moment a negative appears. The transferable lesson is the subtraction itself: when a counting predicate is an equality and therefore won't slide, look for a hereditary relaxation of it ('at most k') and difference two of them.

WATCH THE IDEA RUN

0lo hi

subarrays so far 0

exact starts here (hi − lo) 0

Goal: 2. Two left edges. `lo` is the furthest-back start still worth ≤ 2; `hi` is the furthest-back start that has already dipped under it. The starts between them are the ones that land exactly.

step 1 / 24

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Exactly = AtMost Minus AtMost

YOU'LL SEE IT AGAIN WHEN

You're counting subarrays or substrings that hit some quantity exactly, and the quantity only grows as the window widens.
The 'at most k' version of the same question is obviously slideable, even though the exact version isn't.
For a given right end, the valid starts form a contiguous block rather than a single index — usually because zero-cost elements sit at the boundary.
The quantity is integer-valued, so 'at most k' minus 'at most k−1' isolates 'exactly k' with nothing left over.

SAME BLUEPRINT, DIFFERENT PROBLEM

Subarrays with K Different IntegersCount Number of Nice SubarraysSubarray Sum Equals KSubarray Product Less Than K

The bar isn't "solved it once." It's "could rebuild it from the observation."