# Cumulative Sum

> The total grows with every row.

Canonical URL: <https://datadriven.io/problems/cumulative_sum>

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

Given a list of numbers, return a list where position i equals the sum of input[0..i] (inclusive).

## Worked solution and explanation

### Why this problem exists in real interviews

Running-total is the prefix-sum setup question: interviewers use it as a warmup before the harder prefix-sum problems (subarray-sum-equals-k, range queries, etc). The coding answer is one loop with an accumulator; the grading is on whether you produce output in one pass, handle the empty list without a special case, and know the itertools.accumulate shortcut for the bonus points.

---

### Break down the requirements

#### Step 1: Maintain a running total in one pass

Initialize total = 0, loop over nums, update total += x, append total to the output list. Single pass, no nested loops. The naive O(n^2) is sum(nums[:i+1]) for each i, which recomputes the same sums repeatedly and is a red flag at any level above junior.

#### Step 2: Preallocate or append; both are O(n)

Python list.append has amortized O(1) cost, so the append-in-loop version hits O(n) total. Preallocating [0] * len(nums) and assigning by index is the same asymptotic cost but uses more code. Append is cleaner and equally fast.

#### Step 3: Return [\] for empty input with no branch

Looping over [] produces no iterations, the output list stays [], the return value is []. No 'if not nums: return []' branch needed. Writing it is a tell that you do not trust the loop.

---

### The solution

**Accumulate in one pass**

```python
def running_total(nums):
    out = []
    total = 0
    for x in nums:
        total += x
        out.append(total)
    return out
```

> **Cost Analysis**
>
> Time is O(n) with one pass, one add per element, one append per element. Space is O(n) for the output. itertools.accumulate(nums) is the same O(n) in C and slightly faster in practice; list(accumulate(nums)) is a one-line alternative that interviewers appreciate seeing when the candidate knows it exists.

> **Interviewers Watch For**
>
> Whether you write O(n) or the O(n^2) slice-and-sum trap, whether you know itertools.accumulate, and whether you handle empty lists without a branch. Strong candidates mention that accumulate takes a binary function (accumulate(nums, func=max) gives running max), which is the generalization behind the prefix-sum family of problems.

> **Common Pitfall**
>
> The classic O(n^2) solution: [sum(nums[:i+1]) for i in range(len(nums))]. It looks clean and passes small test cases, but on 10k elements it is already 50 million operations. The fix is the running accumulator. Another miss: mutating nums in place (nums[i] += nums[i-1]) which violates 'return a new list' and also trips up callers who still hold the original reference.

---

## Common follow-up questions

- Rewrite this using itertools.accumulate. _(from itertools import accumulate; return list(accumulate(nums)). Discuss why it is slightly faster (C implementation) and when to use the explicit loop (custom behavior, early exit).)_
- How would you support a running product instead of a running sum? _(accumulate(nums, operator.mul) or a manual loop with total *= x and initial total = 1. Mention that empty input must return [] (not [1]) to match the additive contract.)_
- How would you compute the running total over a 10 GB file of numbers? _(stream line by line, accumulate as you go, write output line by line; never materialize the full list. Mention numpy.cumsum for in-memory numeric arrays.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/cumulative_sum)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.