The Missing Empty Prefix
Counting contiguous subarrays whose sum equals k, using prefix sums in a hash map. It returns 3 for a = [2, 3, 1, 4, -4, 5], k = 5, but the true count is 4.
def count_subarrays(a, k):
counts = {}
total = 0
result = 0
for x in a:
total += x
result += counts.get(total - k, 0)
counts[total] = counts.get(total, 0) + 1
return result
Which subarray is missed, and what is the fix?
Sign in to answer questions and track your progress
Sign In