Module 01 · Execution Grammar and State Mutation

010. Peak Active Balance

Interview · Download this solution · All solutions and shared helpers

Problem

Given an ordered list of +1 and -1 events, return the maximum cumulative balance, including the initial balance zero. Events are applied in the given order. Negative intermediate balances are permitted in this arithmetic kata; it does not validate a physical resource log.

Examples

Example 1

peak_balance([1, 1, -1, 1, -1])
=> 2

The final balance is one but the peak is two.

Example 2

peak_balance([])
=> 0

The initial state is included.

Example 3

peak_balance([-1, -1])
=> 0

Negative prefixes do not exceed the initial zero.

Reveal the worked solution and reasoning

Why this mechanism works

An event is a delta rather than a complete state. Apply it to the current balance and then compare the resulting state with the maximum. Including the initial state makes an empty or entirely negative sequence return zero. Later sweep-line problems use this same event-to-state transformation.

State and boundaries

active is the balance after consumed events. peak is the maximum balance among the initial state and all consumed prefixes.

Protocol

Initialize active and peak to zero.
Apply each delta to active.
Update peak after applying the event.
Return peak.

Visualization

event:    +1 +1 -1 +1 -1
balance:   1  2  1  2  1
peak:      1  2  2  2  2

Python implementation

def peak_balance(events):
    active = peak = 0
    for delta in events:
        active += delta
        peak = max(peak, active)
    return peak

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

peak_balance([1, 1, -1, 1, -1])

L2 peak_balance: active = peak = 0
events=[1, 1, -1, 1, -1]; active=0; peak=0

L3 peak_balance: for delta in events:
events=[1, 1, -1, 1, -1]; active=0; peak=0; delta=1

L4 peak_balance: active += delta
events=[1, 1, -1, 1, -1]; active=1; peak=0; delta=1

L5 peak_balance: peak = max(peak, active)
events=[1, 1, -1, 1, -1]; active=1; peak=1; delta=1

L4 peak_balance: active += delta
events=[1, 1, -1, 1, -1]; active=2; peak=1; delta=1

L5 peak_balance: peak = max(peak, active)
events=[1, 1, -1, 1, -1]; active=2; peak=2; delta=1

L3 peak_balance: for delta in events:
events=[1, 1, -1, 1, -1]; active=2; peak=2; delta=-1

L4 peak_balance: active += delta
events=[1, 1, -1, 1, -1]; active=1; peak=2; delta=-1

L3 peak_balance: for delta in events:
events=[1, 1, -1, 1, -1]; active=1; peak=2; delta=1

L4 peak_balance: active += delta
events=[1, 1, -1, 1, -1]; active=2; peak=2; delta=1

L3 peak_balance: for delta in events:
events=[1, 1, -1, 1, -1]; active=2; peak=2; delta=-1

L4 peak_balance: active += delta
events=[1, 1, -1, 1, -1]; active=1; peak=2; delta=-1

Result: 2. The final balance is one but the peak is two.

peak_balance([])

L2 peak_balance: active = peak = 0
events=[]; active=0; peak=0

Result: 0. The initial state is included.

Why the solution is correct

The running addition gives the exact balance after each event. Updating the maximum considers every event boundary once, while initialization includes the boundary before any event. Therefore no candidate balance is omitted.

Time and space

O(n) time and O(1) auxiliary space.

Common mistakes

Returning the final balance answers a different question. Checking the peak before updating misses a maximum created by the last event.

Reasoning card

State: active is the balance after consumed events. peak is the maximum balance among the initial state and all consumed prefixes.

Invariant: active is the balance after all processed events.

Decision to rehearse: Apply an event delta, then compare with the best.

Finish: Return peak

Transfer exercise

Return the earliest event index at which the peak occurs, explicitly deciding how to represent an initial-state maximum.