001. Running Total
Problem
Given a mutable list of integers nums, replace nums[i] by the sum of the original values at indices 0 through i, inclusive. Return the same list object. Negative values and an empty list are allowed. Earlier writes must not change which original value is consumed next.
Examples
Example 1
running_total([3, -2, 5, 1])
=> [3, 1, 6, 7]The negative second value decreases the total.
Example 2
running_total([])
=> []An empty input needs no writes.
Example 3
running_total([-2, -3])
=> [-2, -5]Running totals need not increase.
Reveal the worked solution and reasoning
Why this mechanism works
Recomputing a sum for every prefix repeats almost all the work. Adjacent prefixes differ by exactly one incoming value. Keep that difference in one accumulator. Read the current cell before overwriting it; the unread suffix still contains original values. This is the smallest example of an ingest-update-commit loop.
State and boundaries
i is the current input index. total is the sum through i after the addition. nums[:i] contains already committed prefix sums before that iteration.
Protocol
- Set total to zero.
- Visit original values from left to right.
- Add the current value to total.
- Write total into the current cell.
- Return nums after the scan.
Visualization
original: [3, -2, 5, 1]
consumed: 3 + -2 + 5 + 1
committed: [3, 1, 6, 7]Python implementation
def running_total(nums):
total = 0
for i, value in enumerate(nums):
total += value
nums[i] = total
return nums
Worked execution
running_total([3, -2, 5, 1])
L2 running_total: total = 0 nums=[3, -2, 5, 1]; total=0 L3 running_total: for i, value in enumerate(nums): nums=[3, -2, 5, 1]; total=0; i=0; value=3 L4 running_total: total += value nums=[3, -2, 5, 1]; total=3; i=0; value=3 L3 running_total: for i, value in enumerate(nums): nums=[3, -2, 5, 1]; total=3; i=1; value=-2 L4 running_total: total += value nums=[3, -2, 5, 1]; total=1; i=1; value=-2 L5 running_total: nums[i] = total nums=[3, 1, 5, 1]; total=1; i=1; value=-2 L3 running_total: for i, value in enumerate(nums): nums=[3, 1, 5, 1]; total=1; i=2; value=5 L4 running_total: total += value nums=[3, 1, 5, 1]; total=6; i=2; value=5 L5 running_total: nums[i] = total nums=[3, 1, 6, 1]; total=6; i=2; value=5 L3 running_total: for i, value in enumerate(nums): nums=[3, 1, 6, 1]; total=6; i=3; value=1 L4 running_total: total += value nums=[3, 1, 6, 1]; total=7; i=3; value=1 L5 running_total: nums[i] = total nums=[3, 1, 6, 7]; total=7; i=3; value=1
Result: [3, 1, 6, 7]. The negative second value decreases the total.
running_total([])
L2 running_total: total = 0 nums=[]; total=0
Result: []. An empty input needs no writes.
Why the solution is correct
Initially the empty prefix sums to zero. Adding the next original value extends the represented prefix by exactly one element; writing that sum finalizes its answer without touching unread cells. At termination every position has been finalized.
Time and space
O(n) time and O(1) auxiliary space; the supplied list stores the output.
Common mistakes
Writing before adding loses the incoming value. Summing nums[:i+1] after earlier mutations sums prefix sums rather than the original data.
Reasoning card
State: i is the current input index. total is the sum through i after the addition. nums[:i] contains already committed prefix sums before that iteration.
Invariant: total equals the sum of the processed prefix.
Decision to rehearse: Ingest the current value, update state, then commit it.
Finish: Return nums after the scan
Transfer exercise
Return sums of the values strictly before each position. Which comes first now: committing or adding?