Count day-ranges whose PnL equals a target

Question

You have a desk's daily PnL for the year. Count how many contiguous day-ranges sum to exactly k. Count all such ranges in O(n).

Accepted Answer

A range (l, r) sums to k exactly when prefix[r+1] - prefix[l] = k, i.e. prefix[l] = prefix[r+1] - k. So as we stream the running sum, we ask "how many earlier prefixes equal running - k?" A hash map of prefix-value frequencies answers that in O(1). Seed it with {0: 1} to account for ranges that start at day 0. Tracing with k = 6: running sums are 3, 2, 6, 4, 9. At running = 6 we look for 0, found once (the seed), giving the range [3, -1, 4]. At running = 9 we look for 3, found once, giving [-1, 4, -2, 5]. Total 2. Time O(n), one pass, space O(n) for the map. Takeaway. "Count subarrays summing…

Count day-ranges whose PnL equals a target

Your answer

More Coding questions