π± The wrong-tool giveaway
"Count the subarrays that sum to k" β with negative numbers in the input. Candidate A says immediately: "prefix sums with a running total and a map of prefix counts; the negatives rule out a sliding window." Candidate B reached for the window because it worked last round, and spent twenty minutes fighting shrink conditions that cannot work. Pattern recognition is also pattern exclusion: knowing the window needs validity that's monotone as it grows, and that sums with negatives aren't, is the entire diagnosis. A finished with tests traced; B never got a working answer.
π§° What you'll learn
- Prefix sums β O(1) range aggregates from one linear preprocessing pass
- Prefix + hash map β counting subarrays by sum, negatives and all
- Sorting intervals by start β merge, detect conflicts, insert
- Sorting intervals by end β the greedy that keeps the most non-overlapping
- Boundary discipline: touching endpoints, empty inputs, the
{0: 1}seed
Pattern 1 β Prefix sum: pay once, query free
prefix[i] = sum of the first i elements, with prefix[0] = 0. Then
sum(nums[i..j]) = prefix[j+1] β prefix[i]. Anything additive works: vowel
counts, parity counts, balance deltas. The drill-classic variant counts
subarrays summing to k with a hash map from prefix value β times seen: a
subarray ending at i sums to k iff total β k appeared as an earlier
prefix, and the map tells you how many times.
| You see⦠| Think⦠|
|---|---|
| Many "sum/count over range [l, r]" queries, static array | Build prefix once; each query is O(1) |
| "Count subarrays with sum exactly k" (negatives allowed) | Running prefix + hash map of prior prefix counts |
| Range property is additive (vowels, parity, balance) | Binary prefix: 1 where the property holds, else 0 |
| Nested loops recomputing range totals | One prefix pass kills the inner loop |
| Tried a window but values go negative | Prefix + map, not a window |
Template β subarray sum equals k:
def subarray_sum_k(nums, k):
count = total = 0
seen = {0: 1} # empty prefix sums to 0 β seed it
for x in nums:
total += x # prefix sum through x
count += seen.get(total - k, 0) # subarrays ending here with sum k
seen[total] = seen.get(total, 0) + 1
return count
Complexity: O(n) to build, O(1) per range query, O(n) space. For the
counting variant: O(n) time and space, and the {0: 1} seed is what makes
subarrays starting at index 0 count. In fixed-width languages, ask about
magnitudes β prefix sums overflow.
Drills (easy β hard): Range Sum Query β Immutable β Subarray Sum Equals K β Count Vowels in Substrings (batched range queries) β Contiguous Array (equal-count balance as prefix + first-seen map).
Pattern 2 β Intervals: sort, then compare neighbors
The whole game is the sort key. Sort by start to merge or detect conflicts β after start-sorting, an interval can only collide with the block before it. Sort by end to keep the maximum number of non-overlapping intervals: the earliest-ending interval is always a safe first pick, because it frees the timeline soonest. Sorting by end when the problem says "minimum removals" is the tell of someone who drilled this.
| You see⦠| Think⦠|
|---|---|
| "[start, end] pairs β merge overlapping" | Sort by start; extend or append into an output block |
| "Can a person attend all meetings?" | Sort by start; any curr.start < prev.end β no |
| "Minimum removals so none overlap" / "max non-overlapping" | Sort by END; greedy keep |
| "Insert one interval into a sorted, disjoint list" | Three phases: before, merge-overlaps, after |
| "Free time / common gaps across schedules" | Merge everything, then report gaps between blocks |
Template β merge intervals:
def merge_intervals(intervals):
intervals.sort(key=lambda iv: iv[0])
merged = []
for start, end in intervals:
if not merged or start > merged[-1][1]:
merged.append([start, end]) # disjoint: new block
else:
merged[-1][1] = max(merged[-1][1], end) # overlap: extend
return merged
Complexity: O(n log n) β the sort dominates; the merge pass is O(n) with
O(n) output space. Two boundary questions to ask out loud every time: do
touching endpoints overlap ([1,4] and [4,7])? Does the problem want
start > prev_end or >=? Half of all interval bugs live in that one
comparison.
Drills (easy β hard): Can Attend Meetings β Merge Intervals β Non-Overlapping Intervals (sort by end) β Employee Free Time (merge across schedules, then take the gaps).
π€ Coding drill: run it
You are a staff engineer running a timed coding drill at a top tech company. Run one drill
drill with me on PREFIX SUM and INTERVALS.
1. Pick ONE problem that maps to these patterns at senior difficulty.
State it concisely: setup, input, output, one worked example, one
constraint worth noticing. Do not name the pattern it uses.
2. Enforce a 30-minute timer. Warn me at 5 minutes left; stop me at zero.
3. Ask which language I'm using and hold me to it.
4. Hints only when I explicitly ask, one rung at a time, never code:
(a) nudge β restate the constraint or point at a suspicious example;
(b) direction β name the family of approach, not the algorithm;
(c) structure β outline the algorithm's steps in words.
5. Drill like a senior loop: make me restate the problem, state my
complexity unprompted, and trace one example before I call it done.
6. When time is up or I say done, grade 1-5 each: correctness, complexity
analysis, communication, edge cases β one line of evidence per score,
then the single highest-leverage improvement.
Start with the problem statement. No preamble.
β You own it when
- You derive
prefix[j+1] β prefix[i]on paper without hesitating - The
{0: 1}seed and why it exists is a sentence you can say - You switch to prefix+map, not a window, the moment negatives appear
- Start-sort vs end-sort is an automatic choice, justified aloud
- You ask whether touching endpoints overlap before coding intervals
- You state O(n log n) for interval problems and attribute it to the sort
π Jargon
| Term | What it means |
|---|---|
| Prefix sum | Running-total array; any range aggregate becomes a subtraction |
| Seed value | The {0: 1} map entry standing in for the empty prefix |
| Range query | An aggregate question over [l, r] β what prefixes make O(1) |
| Sort key | The field intervals sort on: start for merging, end for greedy keeping |
| Greedy | Take the locally best pick (earliest end) and never reconsider |
| Overlap predicate | The comparison deciding collision β including whether touching counts |
π When it goes wrong
- Blanking. Restate, then enumerate the brute force: "recompute each range, O(nΒ·q) β the repeated work is re-adding the same leading elements." Prefix sums fall straight out of that sentence.
- Wrong pattern. A window over negatives is broken by design. If validity isn't monotone as the window grows, stop β prefix+map territory.
- Off-by-one in indexing. Pick one convention β
prefix[0] = 0, sosum(i..j) = prefix[j+1] β prefix[i]β and write it down before coding. Convention drift is the classic interval bug. - Sort key mismatch. Sorting by start for "max non-overlapping" fails silently when one long early interval blocks the rest. Keeping intervals β sort by end. Merging β sort by start.
- No boundary questions. Not asking about touching endpoints or empty input reads as inexperience. Ask, then code.