With prefix sums, any range total turns into one subtraction: the total before the range ends minus the total before it starts. The leading zero makes ranges that begin at index 0 work like any other. And unlike a sliding window, this approach keeps working when values are negative or zero.
Here’s how the running totals helped in each exercise:
- Range Totals: One pass built the prefix list, and each query became a single subtraction.
- Balanced Position: The overall total, a running left sum, and the current value were enough to get the right sum, so you didn’t need a list at all.
- Totals at Several Widths: One prefix list served every width, so the output size, and not repeated addition, set the cost.
- Exact Signed Total: Looking up an earlier prefix equal to the current prefix minus the target identifies a range. The initial zero covers ranges that start at the beginning.
- Count Exact Totals: Every earlier matching prefix is a separate range, so you needed frequencies instead of just existence.
- Equal Binary Counts: Treating zeros as -1 turns equal counts into a repeated balance. Keeping each balance’s earliest index gives the longest range.
Take another look at the last three exercises. Each one stored a different fact about earlier prefixes: any index, a count, and the earliest index. Picking which fact to keep was the real decision, and it’s a good one to say out loud in an interview.
Off-by-one slips love prefix sums, so if a range came out one element too long or too short, you’re in good company! Those near misses point right at the part of the index math that needs another pass. Pick the exercise that took you the most attempts, and in two or three sentences, explain what first went wrong and what changed your mind.
