Counting with seen prefixes
Sometimes you need how many ranges have a property, not their sums. Fix the end of a range. Its sum is pre[end] - pre[start], so for the sum to equal T the start must satisfy pre[start] = pre[end] - T.
Walk once, and keep a dict of how often each earlier prefix value occurred. At every step: look up the value you need, add its count to the answer, then record the current prefix.
need = total - T answer += seen.get(need, 0) seen[total] = seen.get(total, 0) + 1
For "total is a multiple of m" questions, store the prefix remainder (total % m) instead. Two prefixes with the same remainder differ by a multiple of m.
Order matters. Look up before you record, otherwise a range could pair with itself or be empty. If the statement limits the range length (say, at least 2), delay recording by that many steps.
In the visual, seen counts earlier totals. Each match is one range whose steps sum to 0.
See it run
steps = [1, -1, 1, -1] total = 0 seen = {0: 1} for s in steps: total = total + s print(seen.get(total, 0)) seen[total] = seen.get(total, 0) + 1
seen starts with {0: 1}: the empty prefix before the first step.
Practice counting with seen prefixes
Exercise 1
A turnstile logs the badge number of each person entering: badges. Return a list of the same length where entry i is the number of earlier positions (before i) that hold the same badge number as badges[i]. An empty list gives [].
Constraints: 0 ≤ len(badges) ≤ 10^5, 1 ≤ badges[i] ≤ 10^9.
Example: solution([7, 3, 7, 7, 3]) returns [0, 0, 1, 2, 1].
Exercise 2
A packing line receives boxes in order, weights[i] kg each. A bundle is a stretch of at least 2 consecutive boxes. Count the bundles whose total weight is a multiple of m kg. Bundles at different positions are different bundles, even if the weights are the same. A single box is not a bundle.
Constraints: 0 ≤ len(weights) ≤ 10^5, 0 ≤ weights[i] ≤ 10^4, 1 ≤ m ≤ 10^4.
Example: solution([3, 5, 2, 6], 4) returns 3: the bundles [3, 5] (8), [2, 6] (8) and [3, 5, 2, 6] (16). solution([4, 4, 3], 4) returns 1: only [4, 4]. A lone 4 does not count.
Exercise 3
A thermostat logs the temperature change for each minute: changes[i] (it can be negative). Find the stretch of consecutive minutes whose changes add up to exactly target and that ends earliest (the smallest last index). If several stretches end at that same minute, choose the shortest one. A stretch has at least one minute.
Return [start, end] using minute indices, both included, or [-1, -1] if no stretch adds up to target.
Constraints: 0 ≤ len(changes) ≤ 10^5, -1000 ≤ changes[i] ≤ 1000, -10^9 ≤ target ≤ 10^9.
Example: solution([2, -1, 3, 1, -2, 4], 4) returns [0, 2] (2 - 1 + 3). solution([1, -1, 2], 2) returns [2, 2]: both [0, 2] and [2, 2] add up to 2 and end at minute 2, and the shorter one wins. solution([1, 1, 1], 5) returns [-1, -1].
The explanation and tasks are public. Running this lesson requires an account with course access.
Practice
Loading Python…Visualizer Watch your code run line by line
Run your code, then choose Play to follow its execution.