Product of array except self
StopTrace
- CH3 suffix
19/19
Running products from each end: everything left of i, times everything right of it.
Step through it →Prefix Sums
A prefix sum is the running total up to each point, so any stretch's sum is one subtraction: the total at its end minus the total before its start.
Subarray sum equals k: count the stretches that add up to k
StopTrace
numsk
frequency starts as {0: 1}: the empty prefix, before any number, sums to 0.
Typical cost O(n) preprocessing, O(1) per queryFull lesson: Subarray Sum Equals K →
When to reach for it
- The question is about sums or counts over contiguous stretches.
- You answer many range questions about one array that doesn't change.
- Numbers can be negative, so a sliding window can't tell when to shrink.
- Each answer combines everything to its left with everything to its right.
What stays true
The map starts as {0: 1}, and each total is recorded right after its lookup. So a lookup at i sees every earlier boundary, the start of the array included, and never i itself.
The map counts every boundary so far
StopTrace
Invariantfrequency counts every prefix sum read so far, starting with the empty prefix's 0.✓ Holds
frequency starts as {0: 1}: the empty prefix, before any number, sums to 0.
Break it
Each input here has tripped up a version of this code. The stage runs the one that gets it right.
Without the {0: 1} seed, [3, 4] has no earlier total to match, and the count comes out 1, not 2.
Subarray sum on the inputs that trip it up
StopTrace
frequency starts as {0: 1}: the empty prefix, before any number, sums to 0.
Answer2Steps11
Variants
The code
The same algorithm in plain Python. The lit line is the one the current frame came from.
Subarray sum equals k: count the stretches that add up to k
StopTrace
frequency starts as {0: 1}: the empty prefix, before any number, sums to 0.
subarray_sum.py
def subarray_sum(nums, k): frequency = {0: 1} current = answer = 0 for x in nums: current += x answer += frequency.get(current - k, 0) frequency[current] = frequency.get(current, 0) + 1 return answerDrill it
Product of Array Except SelfRuns live,MediumSubarray Sum Equals KRuns live,Medium
Range Sum Query - ImmutableEasy
Contiguous ArrayMedium