Algorithms · interview field notes

Permit Streaks: counting the ranges that sum to target

A daily feed of building-permit counts — zeros allowed, corrections can go negative. The ask: how many contiguous date ranges sum to exactly target? This is a guided walk-through — press Play on each figure, and leave able to explain the O(n) trick, not just type it.

counts = [3, 4, 7, 2, −3, 1, 4, 2], target = 7 → 4 ranges

How do you count them without checking all O(n²) ranges?

Why can't you just slide a window across the feed?

The answer to memorize

Turn it into a prefix-sum lookup

The one sentence to keep in your pocket — say it cleanly and stop:

Say this

"Keep a running prefix sum and a hash map of how often each prefix has appeared. At each day, the number of ranges ending there equals map[sum − target]. One pass — O(n) time, O(n) space."

That's the whole solution. The rest of this page is why it works and how to defend it under pressure — including the question that separates a junior answer from a senior one: why not just slide a window?

The obvious way, and its ceiling

Brute force: every range

Start simple. There are about n²/2 contiguous ranges; score each one against target. Correct, easy to write — and quadratic.

Brute force · score every rangefig

4-3

ranges scored

matched target

Brute force treats every contiguous range as a candidate. For 8 days that's 36 ranges to score.

01 / 10

Two nested loops = O(n²). The fix isn't a cleverer loop — it's reframing the question so each day's answer is a single lookup.

The reframe

A range is one subtraction

The whole trick rests on one identity. Precompute running totals, and the sum of any range becomes the difference of two of them — no re-adding.

The prefix-sum identityfig

daily counts

3472-3142

Lay the daily counts in a row — the same feed, now read left to right.

01 / 04

The move

We want every pair where P[i] = P[j+1] − target. Instead of searching for those pairs, we'll remember the prefixes we've seen and look each one up in O(1).

The payoff

One pass with a hash map

Sweep left to right. Carry the running prefix sum and a map of how many times each prefix value has occurred. At each day, the ranges ending there are already counted in the map.

One pass · count earlier prefixes equal to (sum − target)fig

4-3

running sum

− 7 =

look up

—

prefix sums seen → how many times

0×1

answer · matching ranges

Initialize one map holding {0: 1} — the empty prefix, seen once. (That seed is what lets a range starting on day 0 get counted.) sum = 0, answer = 0.

01 / 09

Each day is O(1): one add, one lookup, one insert. n days ⟶ O(n) time, O(n) space. That's the answer the interviewer is fishing for.

The senior tell

Why not a sliding window?

The instinct for "contiguous range summing to target" is two pointers. Here it's a trap — and naming why earns the most points in the whole problem. Flip the toggle and watch the prefix sum.

Why a sliding window fails herefig

3472-3142

A correction (−3) makes the prefix dip. Now extending the window can lower the sum, so "too big ⟹ shrink" is no longer valid — there's no monotonic signal to steer the pointers. The sliding window is unsound the moment a value can be zero or negative.

the permit feed allows zero and negative days — so prefix-sum + hashmap is the right tool, not two pointers

Say this when asked "could you use a sliding window?"

"Only if every count were non-negative — then the prefix sum is monotonic and two pointers work in O(n). But the feed allows zeros and negative corrections, so the sum isn't monotonic and the window can't decide when to shrink. That's why I reach for the prefix-sum map."

What trips people up

The edge cases that break naive code

Four traps an interviewer will probe — each one is handled for free once the prefix-sum map is set up correctly.

seed the map with {0: 1}

Without it, ranges that start at day 0 (where the whole prefix already equals target) go uncounted. Seed before the loop, not inside it.

negatives & zeros

A zero-sum stretch or a correction means the same prefix value recurs. The map stores a count, not a boolean — add that count to the answer, don't just check membership.

target = 0

Perfectly valid. A run like [2, −2] sums to 0 and must be counted; the same machinery handles it with no special case.

order matters

Add to the answer before inserting the current prefix — otherwise a single element equal to target gets matched against itself. Look up, then record.

Print this on the back of your hand

The interview cheat-sheet

“What's the approach?”

Prefix sums + a hash map of counts. Walk once; at each day add map[sum − target] to the answer, then bump map[sum]. O(n) time, O(n) space.

“Why does that work?”

A range i…j sums to target ⟺ P[i] = P[j+1] − target. So the count of valid ranges ending here is just how many earlier prefixes equal sum − target.

“Why not a sliding window?”

Two pointers need a monotonic running sum. Zeros and negative corrections break that — the sum can fall as the window grows. State this up front; it's the senior tell.

“Don't forget…”

Seed {0: 1}, store counts (not seen/unseen), and look up before inserting. target = 0 works with no special case.

The one-liner to land

"I keep a running prefix sum and a map of how often each prefix has occurred. The number of ranges ending at the current day is map[sum − target] — one pass, O(n). A sliding window won't work because the feed allows zeros and corrections, so the sum isn't monotonic."