Minimum Value to Get Positive Step by Step Sum (LeetCode 1413)

The problem

You pick a positive integer startValue, then add the numbers of nums to it one at a time, left to right. After every addition the running total must be at least 1. Return the smallest startValue that makes this true.

Input:  nums = [-3, 2, -3, 4, 2]
Output: 5

Starting at 5 the totals are 2, 4, 1, 5, 7, all at least 1. Starting at 4 the third total would be 0.

How to think about it

Start with brute force. Try startValue = 1, 2, 3, … and simulate each one until a start survives. Each simulation is O(n) and the answer can be as large as the sum of all the negatives, so this can be very slow.

The key insight: the start value just shifts every prefix sum. The running total after step k is startValue + pre[k], where pre[k] is the plain prefix sum of nums. Every one of those must be at least 1, so the only one that matters is the lowest prefix sum, lo. You need startValue + lo >= 1, which gives startValue = 1 - lo.

Why start lo at 0? startValue must be at least 1 even if every prefix sum is positive. Treating the empty prefix (sum 0) as a candidate gives 1 - 0 = 1 in that case.

Which pattern is this? Prefix sums with a running minimum. The tell is “the running total must never drop below …”: only the worst point of the prefix curve matters.

Approach

1. Set s = 0 (running sum) and lo = 0 (lowest sum seen, including the empty prefix).
2. For each x, add it to s and update lo = min(lo, s).
3. Return 1 - lo.

Solution

def min_start_value(nums):
    s = 0; lo = 0                  # lo starts at 0 so the answer is never below 1
    for x in nums:
        s += x; lo = min(lo, s)    # track the deepest dip of the prefix sum
    return 1 - lo                  # lift that dip to exactly 1
# min_start_value([-3,2,-3,4,2]) -> 5

Dry run

nums = [-3, 2, -3, 4, 2]:

The deepest dip is -4, so the answer is 1 - (-4) = 5.

Complexity

• Time: O(n). One pass over the array.
• Space: O(1). Two integers.

Edge cases and pitfalls

• All positive numbers ([1, 2]) return 1, because lo never drops below its starting 0.
• Initialising lo to nums[0] or inf is a common bug: with all-positive input it would return 0 or a negative number, which is not a positive start value.
• Off by one: the total must be at least 1, not at least 0, hence 1 - lo and not -lo.
• Simulating start values one by one is the slow wrong approach; one pass gives the answer directly.

Related problems

• Find Pivot Index (LeetCode 724): another single running-sum variable instead of a full prefix array.
• Best Time to Buy and Sell Stock (LeetCode 121): also tracks a running minimum in one pass.
• Maximum Subarray (LeetCode 53): reasoning about the shape of a running sum.