progress

~/problems / Arrays & hashing / Python toolkit

Running balance and peak with accumulate

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

easy ~10 min

An account starts at start and then sees a list of deposits (positive) and withdrawals (negative). Write balance_history(start: int, changes: list[int]) -> tuple[list[int], list[int]] that returns two lists, (balances, peaks), each of length len(changes) + 1:

  • balances[0] == start, and balances[i] is the balance after the first i changes;
  • peaks[i] is the highest balance seen so far: the largest of balances[0] to balances[i].
balance_history(100, [20, -50, 10, 40])
# ([100, 120, 70, 80, 120], [100, 120, 120, 120, 120])

balance_history(-5, [-3, 10])
# ([-5, -8, 2], [-5, -5, 2])

balance_history(7, [])
# ([7], [7])
  • 0 <= len(changes) <= 2 * 10^5; start and each change are in [-10^9, 10^9].
  • Don't modify changes.

⭐ Bonus: recomputing start + sum(changes[:i]) for every i is O(n²) and still passes; a speed test with 200,000 changes earns a star in O(n).

Show hint

itertools.accumulate(changes, initial=start) yields the running totals with start in front. Passing max as the function, accumulate(values, max), yields a running maximum.

Topic: Python toolkit. Counter, deque, heapq, bisect, itertools: the standard library to know cold, and its traps.

0:00
Ctrl ' run · Ctrl ↵ submit
esc