Two versions that return exactly the same list — the largest number seen so far, at every position. Count how many comparisons each one makes on a hundred numbers.
# Re-scans the whole prefix at every step
def running_max(numbers):
return [max(numbers[:i + 1]) for i in range(len(numbers))]
# 100 items -> 1 + 2 + 3 + ... + 100 = 5,050 comparisons
# Carries the best so far forward
def running_max(numbers):
best = float('-inf')
result = []
for number in numbers:
best = max(best, number)
result.append(best)
return result
# 100 items -> 100 comparisons
- Same answers, different curve
At a hundred items the difference is invisible. At a hundred thousand it is five billion comparisons against a hundred thousand, and the first version stops being a function and becomes an outage. Nothing in the code looks slow — the cost is hidden inside max(), which quietly walks the whole slice every time round the loop.
- The slice copies as well
numbers[:i + 1] does not just read the prefix, it builds a new list holding it. So the first version also allocates and throws away n lists on the way to the answer. Any time you slice inside a loop over the same sequence, check whether you are copying the data once per iteration.
- One variable outside the loop is the whole technique
total lives across iterations and remembers what has happened so far; each step does the small amount of new work and moves on. That shape — an accumulator initialised before the loop, updated inside it — is the same one behind counting, running totals, and every fold or reduce you will meet later under a fancier name.
Keep the total so far in a variable that lives outside the loop. Each number adds to it, and the new value is what goes into the result.
Start total at 0 and result at []. For each number: add it to total, then append total to result. The order matters — appending before adding gives you the total before this item rather than including it.
Resist any version that calls sum() inside the loop; it recomputes work you already have. If you want the one-liner, itertools.accumulate(numbers) does exactly this — remember it returns an iterator, so wrap it in list().
def running_total(numbers): total = ____ result = [] for number in numbers: total ____ number result.append(____) return result
def running_total(numbers):
total = 0
result = []
for number in numbers:
total += number
result.append(total)
return result
Swap the two lines and you get the total *before* each item — which is a genuinely useful function called an exclusive prefix sum, and not the one the contract asked for. The two differ by one position and produce lists of the same length, so nothing about the shape of the answer will tell you which one you wrote. Only a case with distinguishable numbers will.
total += number rebinds a local name; it never reaches into the caller’s list. The in-place version, numbers[i] += numbers[i - 1], is one character away in spirit and edits data the caller still owns. When a function’s answer is derived from its input, build a new container rather than overwriting the old one.
Precomputing a running total turns 'sum of items i through j' into totals[j] - totals[i - 1] — one subtraction instead of a scan, which is the trick behind range queries, image integral tables and a good deal of competitive programming. Building the table costs one pass; every question afterwards is free.
Every version below is correct and verified against the same cases by the build. They are here because knowing which one to reach for is the part that takes judgement, and the trade-off is stated rather than left for you to guess.
from itertools import accumulate
def running_total(numbers):
return list(accumulate(numbers))
What to write in real code. It is the same loop in C, it handles the empty case for free, and swapping the operator gives you running maximum, minimum or product without a rewrite. The list() is not optional — accumulate returns an iterator, and returning that instead would give a caller something they can only consume once.
def running_total(numbers):
return [sum(numbers[:index + 1]) for index in range(len(numbers))]
Correct on every case here, and quadratic. It reads well, which is exactly why it survives code review and then turns up in a profiler two years later attached to a list nobody expected to grow. The give-away is a slice of the loop’s own sequence inside the loop — that pattern is nearly always re-doing work the previous iteration already did.
In real code, itertools.accumulate is this function, already written and tested — and it takes an operator, so accumulate(numbers, max) gives the maximum so far and accumulate(numbers, operator.mul) the running product. For anything numeric and large, numpy.cumsum does it in compiled code over a whole array. Write the loop when you want the answer to be readable to someone who has not met accumulate, or when each step needs to do more than add — logging, clamping, or stopping early.
- Add a start argument so the totals begin from an opening balance, and check what it should do to an empty input.
- Write running_max alongside it, then look at how much of the two functions is identical and what it would take to write one function that does both.
- Use your result to answer 'what is the total between positions i and j' without re-scanning, and work out the off-by-one in the subtraction.