Running Ledger Totals

EasyArrays & Hashing

Problem

A shop's ledger records each day's net cash movement: positive for income, negative for expenses. The owner wants to see the balance at the end of every day, starting from zero.

Given nums, return an array totals of the same length where totals[i] = nums[0] + nums[1] + … + nums[i].

Example 1

Input:
nums = [3, -1, 4, 2]
Output:
[3, 2, 6, 8]

3, then 3 - 1 = 2, then 2 + 4 = 6, then 6 + 2 = 8.

Example 2

Input:
nums = [5]
Output:
[5]

Example 3

Input:
nums = []
Output:
[]

Constraints

  • 0 ≤ nums.length ≤ 10^5
  • -10^4 ≤ nums[i] ≤ 10^4

Hint

Show the first hint

How is totals[i] related to totals[i - 1]?

Walkthrough

How to approach it

01Clarify before coding

  • Should the output include a leading 0 for 'before day one'? No: same length as nums, totals[0] = nums[0].
  • Can values be negative? Yes; the running sum may go down or below zero.
  • Can I overwrite nums in place? Ask; returning a new array is the safe default.

02Brute force

For each i, sum nums[0..i] from scratch.

Cost: O(n²) time: about 5·10^9 additions for n = 10^5, because every prefix is re-added from the start.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.