# Carrying Forward

> The total grows with every row.

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

Domain: Python · Difficulty: medium · Seniority: L3

## Problem

You're rolling a ledger of daily deposits into a running account balance for a dashboard. Given the `deposits` in the order they landed, return the balance standing after each one.

## Example 1

Input:

```
deposits = [1,2,3,4]
```

Output:

```
[1,3,6,10]
```

## Example 2

Input:

```
deposits = []
```

Output:

```
[]
```

## Worked solution and explanation

### What this really is

This is a prefix sum wearing a ledger costume. The skill being probed: can you carry state across a single pass instead of recomputing it? Anyone can produce the right numbers. The trap is reaching for sum(deposits[:i+1]) at each position, which re-adds the same prefix over and over and turns an O(n) walk into O(n^2) that quietly dies on a 10k-element ledger. Get the accumulator right and the empty list falls out for free, no special case.

---

### Break down the requirements

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

Initialize total = 0, loop over deposits, update total += amount, append total to the output list. Single pass, no nested loops. The naive O(n^2) is sum(deposits[:i+1]) for each i, which recomputes the same prefixes 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(deposits) 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 deposits: 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(deposits):
    balances = []
    total = 0
    for amount in deposits:
        total += amount
        balances.append(total)
    return balances
```

> **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(deposits) is the same O(n) in C and slightly faster in practice; list(accumulate(deposits)) 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(deposits, func=max) gives a running max), which is the generalization behind the prefix-sum family of problems.

> **Common Pitfall**
>
> The classic O(n^2) solution: [sum(deposits[:i+1]) for i in range(len(deposits))]. 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 the input in place (deposits[i] += deposits[i-1]), which violates 'return a new list' and 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(deposits)). 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 total? _(accumulate(deposits, operator.mul) or a manual loop with total *= amount 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/carrying_forward)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.