Challenge: subarray sums (boss)
Count contiguous subarrays summing to k — using prefix sums and a hash map.
- Combine prefix sums with a hash map for an O(n) count
- See why running totals + lookups beat re-summing every range
Optional challenge — the boss. This one rewards a real insight. The efficiency check (read-counting, no timing) rejects the O(n²) approach, so you'll need the clever one.
Count how many contiguous subarrays sum to exactly k. Numbers may be
negative. For [1, 1, 1] with k = 2, the answer is 2 (the two adjacent
pairs).
Summing every range is O(n²). The O(n) solution is one of the most satisfying patterns in all of algorithms: prefix sums plus a hash map.
Idea: keep a running total as you sweep. A subarray ending at the current
position sums to k exactly when some earlier running total equals
current_total − k. So count how many times each running total has occurred (in
a dict), and at each step add the number of times current_total − k has been
seen. Seed the dict with {0: 1} so subarrays starting at index 0 are counted.
Write subarray_sum_count(nums, k): the number of contiguous subarrays whose elements sum to k. Numbers can be negative. Aim for O(n) with prefix sums + a dict.
subarray_sum_count([1, 1, 1], 2) → 2subarray_sum_count([1, -1, 0], 0) → 3If you crack this one, you've internalised prefix sums and hashing working together — a pairing that unlocks a huge family of "do it in one pass" problems. That's a fitting place to end the track.