1005EasyArrayPrefix Sum

The Smallest Opening Balance That Never Dips

Tracked in this browser only

Trains the technique from

LeetCode 1413Minimum Value to Get Positive Step by Step Sum

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

An account is opened holding some whole amount, and then the entries of changes are applied to the balance one at a time, in the order given.

Return the smallest opening amount, itself at least 1, that leaves the balance at 1 or more after every entry has been applied.

Examples

Example 1

Input: changes = [-4, 3, -4, 5, 3]
Output: 6

The running totals of the entries are -4, -1, -5, 0 and 3, so the deepest the balance ever sits below its opening amount is five. Opening with six leaves the balance at one at that lowest point, and opening with five would leave it at nothing.

Example 2

Input: changes = [2, 5]
Output: 1

Both entries add, so the balance only climbs and the smallest allowed opening amount already works.

Example 3

Input: changes = [2, -3, -4]
Output: 6

The running totals are 2, -1 and -5, and the last of those is the deepest, so the opening amount has to cover five and leave one over.

Constraints

1 <= changes.length <= 100
-100 <= changes[i] <= 100

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_start_value(changes: list[int]) -> int:

Java

public int minStartValue(int[] changes)

The intended approach

Time O(n) over the log's length.Space O(1).

Run through the entries keeping the total of the changes applied so far. Whatever the opening amount turns out to be, the balance after any entry is that opening amount plus the running total at that point, since the entries do not depend on the balance. So the balance stays at one or more throughout exactly when the opening amount is at least one more than the deepest the running total ever sinks below nothing. One pass finds that deepest point. The answer is that requirement, but never below one, because the opening amount has to be at least one in its own right and a log that only ever gains needs nothing more than that.

Pythonentry point: min_start_value

def min_start_value(changes):
    running = 0
    lowest = 0
    for change in changes:
        running += change
        if running < lowest:
            lowest = running
    need = 1 - lowest
    return need if need > 1 else 1

The obvious version

Try opening amounts from one upwards. For each, walk the whole log applying the entries and watching whether the balance ever falls below one, and return the first amount that survives the walk. Costs a walk of the log per candidate rather than a single pass.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_start_value(changes):
    start = 1
    while True:
        balance = start
        ok = True
        for change in changes:
            balance += change
            if balance < 1:
                ok = False
                break
        if ok:
            return start
        start += 1

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in