Visualized DSA Strategies

Episode 3 Prefix Sums

1 h 8 min · Go · Quiz

Episode 3Prefix Sums

▶ This video is coming to YouTube soon.

The complete guide to prefix sums for coding interviews, in Go. First how a prefix array is built and why it has one extra slot; the four questions a running total answers; what each approach costs; the Go for prefix and difference arrays (make for zeroed slices, a 2D grid made row by row, a map whose missing keys read 0, the comma ok form when 0 is a real index, and a 64-bit int); and five traps. Then nine types, each worked as a small problem in full: examples, the brute force animated beside the running line of code, the complete code, every line explained, and the prefix-sum solution the same way.

What you'll learn

  • How a prefix array turns any range sum into one subtraction
  • Why the array has n + 1 slots and starts with 0
  • Left total against right total with a running sum
  • Counting subarrays that sum to k with a prefix map
  • Prefix remainders and balances: the same prefix twice means a range between
  • Prefix and suffix products without division
  • A difference array for many range updates
  • 2D prefix sums and the four-corner formula
  • Running maximums from both sides: trapping rain water

Chapters

  1. 0:00Intro
  2. 0:24Build a prefix array
  3. 1:45Four questions prefix sums answer
  4. 2:23What each approach costs
  5. 3:08Prefix sums in Go
  6. 5:04Five traps
  7. 6:10Nine prefix-sum types
  8. 6:52Type 1 · Sum of a range, many times
  9. 12:43Type 2 · Where the two sides balance
  10. 19:00Type 3 · Count subarrays that add to k
  11. 25:30Type 4 · A subarray that's a multiple of k
  12. 32:22Type 5 · Equal zeros and ones
  13. 39:25Type 6 · Product of everything else
  14. 46:00Type 7 · Many range updates, one sweep
  15. 52:23Type 8 · The sum of a rectangle
  16. 59:29Type 9 · How much rain is trapped
  17. 1:06:00Spot the type
  18. 1:06:48Quiz: which type?
  19. 1:07:36Recap

Quiz: test yourself

The 5 questions from the end of the episode. Pick an answer to see why it's right.