Count sales stretches that add up to a target

Arrays, strings and hash maps Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

from collections import Counter
seen = Counter({0: 1})
total = hits = 0
for x in [1, 2, 1, 2]:
    total += x
    hits += seen[total - 3]
    seen[total] += 1
print(hits)

Options321

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 3

Right: [1, 2], [2, 1] and [1, 2] at the end each add up to 3.

Prefix totals run 1, 3, 4, 6; the hits come at totals 3, 4 and 6, because 0, 1 and 3 appeared before them.

Why not the others?

B 2. That misses one of the three stretches; the last [1, 2] counts too.
C 1. Only the first stretch would count if the map were never updated.

30-second answer

Keep a running total and a map from each running total to how many times it has appeared. A stretch ending today sums to k exactly when an earlier running total equals today's total minus k, so add that count. One pass, O(n) time and O(n) space. Negative numbers rule out a sliding window, which is why the map is needed.

Practise saying it · 60 s. No recording, just a timer

Explain the prefix-sum trick for counting stretches.

Say your answer out loud, then check which of these points you covered:

Stretch sum = prefix difference
Map of prefix counts seeded with 0
Why a sliding window fails with negatives

Deep dive

The total of days i+1..j equals prefix[j] - prefix[i]. Asking for k is asking how many earlier prefixes equal prefix[j] - k.

Seed the map with {0: 1} so stretches that start on day 0 are counted.

With only non-negative sales, a sliding window also works in O(1) space; refunds break the 'grow right, shrink left' logic.

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

def count_stretches(sales: list[int], k: int) -> int:
    seen: dict[int, int] = {0: 1}
    total = hits = 0
    for x in sales:
        total += x
        hits += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return hits

Common mistakes

Forgetting the {0: 1} seed, which misses every stretch starting at the first day.
Updating the map before reading it, which counts an empty stretch when k is 0.

Senior take & follow-ups

Name the identity (stretch sum = difference of prefixes) before writing code. It turns a puzzle into a lookup.

Follow-up questions

Think of your answer first, then open the hint.

How would you return the longest such stretch instead?
Show hint
Store the first index of each prefix total and take j minus that index.
What if k is 0?
Show hint
The same code counts stretches with zero net sales; the read-before-write order matters most here.

What each operation costs: Arrays · Dynamic Arrays · Hash Table · Hash Functions

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.