A shop records its net sales for each day. Refunds can make a day's number negative. Write a function that counts how many stretches of consecutive days have sales that add up to exactly target.
A stretch is one or more days in a row. Two stretches are different if they start or end on different days.
text
1count_target_stretches([3, 4, 7, -2, 2], 7) -> 3
2count_target_stretches([1, 1, 1], 2) -> 2
3count_target_stretches([0, 0], 0) -> 3
The stretches that add up to 71 / 3
3
0
4
1
7
2
-2
3
2
4
3 + 4 = 7
In the first example, the stretches are [3, 4], [7] and [7, -2, 2]. In the third, each single day sums to 0, and so do both days together.
Write count_target_stretches(daily, target) in Python or countTargetStretches(daily, target) in JavaScript.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 20 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
Brute force first
Try every start day and every end day, adding as you extend the end. That's O(n²) time. It's a fine first answer to state. Because values can be negative, a "sliding window" that shrinks when the sum gets too big won't work here.
Step 2
Prefix sums
Let prefix[k] be the total of the first k days (prefix[0] = 0). The sum of days i through j is prefix[j + 1] - prefix[i]. So a stretch ending at day j hits the target exactly when some earlier prefix equals prefix[j + 1] - target.
0
1
2
3
4
5
prefix
0
3
7
14
12
14
Days 2 to 4 add up to prefix[5] − prefix[2] = 14 − 7 = 7.
Step 3
Count earlier prefixes with a hash map
Walk through the days keeping the running total. Before moving on, ask a map: "how many earlier prefixes equal running - target?" Add that number to the answer. Then record the current running total in the map.
Step 4
Don't forget the empty prefix
Start the map with {0: 1}. That represents "before day 0", and it's what lets a stretch starting on the very first day be counted.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Keep a running total and a map from each prefix total to how many times it has appeared, starting with {0: 1}. For each day, add it to the running total, add count[running - target] to the answer, then increase count[running] by one.
python
1def count_target_stretches(daily, target):
2 seen = {0: 1} # prefix total -> how many times it has appeared
↑the empty prefix: "before day 0"
3 running = 0
4 count = 0
5 for sales in daily:
6 running += sales
↑total of all days so far
7 count += seen.get(running - target, 0)
↑earlier prefixes that make a stretch hit the target
8 seen[running] = seen.get(running, 0) + 1
↑record this prefix AFTER counting
9 return count
javascript
1function countTargetStretches(daily, target) {
2 const seen = new Map([[0, 1]]) // prefix total -> how many times it has appeared
↑the empty prefix: "before day 0"
3 let running = 0
4 let count = 0
5 for (const sales of daily) {
6 running += sales
↑total of all days so far
7 count += seen.get(running - target) ?? 0
↑earlier prefixes that make a stretch hit the target
8 seen.set(running, (seen.get(running) ?? 0) + 1)
↑record this prefix AFTER counting
9 }
10 return count
11}
Complexity
TimeO(n)SpaceO(n)
O(n) time, one pass with O(1) map work per day. O(n) space for the map of prefix totals.
What we learned
"Sum of a stretch" problems become "difference of two prefix sums", which a hash map can look up.
Sliding windows need values that only grow (all positive). With negatives, reach for prefix sums.
Seed the map with the empty prefix (0 seen once), or stretches that start at the beginning are missed.