Running totals
A running total (a prefix sum) keeps adding as you go and remembers the total at every stop:
total = 0 for t in tips: total = total + t # total now includes t
After the loop body for item i, total is the sum of items 0..i. Nothing is added twice: each step reuses the previous total, so a whole list of totals costs one pass.
Two choices to make every time:
- Does the total include the current item, or is it the total before it? Read the statement for the exact words.
- What is the total before the first item? It is
0.
Negative numbers are fine: the total just goes down. In the visual, total is the only value that changes by hand, and totals is its history.
See it run
tips = [3, 1, 4] total = 0 totals = [] for t in tips: total = total + t totals.append(total)
Each pass adds one tip to total, then saves the new total in totals.
Practice running totals
Exercise 1
A café logs the tips it gets each hour in tips (a refund shows as a negative number). Return a list of the same length where entry i is the total of all tips in the hours before hour i. Entry 0 is therefore 0. An empty list gives [].
Constraints: 0 ≤ len(tips) ≤ 1000, -1000 ≤ tips[i] ≤ 1000.
Example: solution([3, 1, 4]) returns [0, 3, 4]: nothing before hour 0, then 3, then 3 + 1.
Exercise 2
A coin jar starts empty. changes[i] is the net number of coins added to the jar on day i + 1 (negative if coins were taken out). Return the number of the first day after which the jar holds at least goal coins, or -1 if that never happens. Only the total at the end of each day counts.
Constraints: 0 ≤ len(changes) ≤ 1000, -100 ≤ changes[i] ≤ 100, 1 ≤ goal ≤ 10^5.
Example: solution([2, -1, 4, 3], 5) returns 3: the totals after each day are 2, 1, 5, 8. solution([1, 1], 10) returns -1.
Exercise 3
A prepaid transit card changes balance at each stop: steps[i] is the change at stop i (negative for a fare, positive for a top-up). Return the smallest whole starting balance (zero or more) so that the balance is never below zero after any stop. The balance after stop i is the starting balance plus steps[0] through steps[i]. With no stops the answer is 0.
Constraints: 0 ≤ len(steps) ≤ 10^5, -1000 ≤ steps[i] ≤ 1000.
Example: solution([-3, 2, -4, 5]) returns 5: the running changes are -3, -1, -5, 0, so the card must start with 5 to survive the lowest point. solution([4, -1]) returns 0.
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.