Last Minute Notes
  • Github
  • Docs
  • Learn
    @sayanstwt
Lessons
0/15 done
  • Sliding Window
  • Two Pointers
  • Prefix Sum & Hash Map
  • Cyclic Sort
  • Merge Intervals
  • Monotonic Stack
Learn/Data Structures & Algorithms/Arrays & Strings

Prefix Sum & Hash Map

7 min Intermediate 8 steps

Count subarrays that sum to k, even with negative numbers.

k
0
Window sum
1
Grow by one
first element
sum 10121-10
current done skipped
In this lessonStep 1 of 8
  1. The problem
  2. Prefix
  3. Range sum
  4. Look back
  5. Hash map
  6. The seed
  7. Negatives
  8. Recap
Step 1 / 8problem

Negatives break the window

Count subarrays of [1, -1, 0] that sum to 0.

A sliding window needs the sum to move in one direction as it grows. Here adding -1 makes it smaller, so there is no rule for when to shrink.

Key idea

Negative numbers with a sum target rule out the sliding window. Reach for prefix sums.

←→ step·R replay·Space pause

You'll learn

  • See why negative numbers break a sliding window
  • Build a prefix array and answer range sums in O(1)
  • Count subarrays summing to k with a hash map of prefixes
  • Remember the empty prefix seed, 0 → 1
Read the full notesDSA Pattern Playbook, 6.1