LeetCode 1413 - Minimum Value to Get Positive Step by Step Sum

LeetCode Problem 1413

Difficulty: 🟢 Easy
Topics: Array, Prefix Sum

Solution

Problem Understanding

The problem gives us an integer array nums and asks us to determine the minimum positive starting value such that when we repeatedly add elements from nums to this starting value, the running total never drops below 1.

In other words, imagine we begin with some number called startValue. We process the array from left to right, updating a running sum at every step:

running_sum = startValue + nums[0]
running_sum = running_sum + nums[1]
running_sum = running_sum + nums[2]
...

The requirement is strict: at every point during this process, the running sum must remain at least 1. Our task is to find the smallest positive integer that satisfies this condition.

The input array represents changes to the running total. Positive numbers increase the sum, while negative numbers decrease it. Because negative values can make the sum fall below 1, we need to carefully determine how large the starting value must be to prevent that from happening.

The constraints are small:

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

This tells us that the input size is tiny, meaning even less efficient approaches could work. However, we should still aim for the cleanest and most optimal solution.

An important observation is that the only thing that matters is the lowest prefix sum encountered while traversing the array. If at some point the cumulative sum reaches -4, then our starting value must be at least 5 so that the running total becomes 1 at that point.

Several edge cases can trip up a naive implementation. If the array contains only positive numbers, the answer should still be 1, because the problem explicitly requires the starting value to be positive and the running total never drops below 1. Arrays with large negative prefixes can require much larger starting values. Arrays that temporarily dip below zero and later recover are also important, because we must guarantee safety at every step, not just the final sum.

Approaches

Brute Force Approach

A straightforward idea is to try every possible positive starting value beginning from 1.

For each candidate startValue, we simulate the running sum through the entire array. If at any step the sum becomes less than 1, we reject that starting value and try the next one. The first value that successfully survives the whole traversal is the answer.

This approach is correct because it exhaustively checks all positive starting values in increasing order. Since we stop at the first valid one, the returned answer is guaranteed to be minimal.

However, this method can be inefficient because we may repeatedly traverse the array for many candidate values before finding the correct answer.

Optimal Prefix Sum Approach

The key observation is that we do not actually need to test different starting values.

Instead, we can compute the minimum prefix sum of the array.

Suppose the cumulative sum of nums reaches its lowest value at minimumPrefix.

If:

startValue + minimumPrefix >= 1

then the running sum will never go below 1.

Rearranging:

startValue >= 1 - minimumPrefix

Thus:

• If the minimum prefix sum is negative, we need enough starting value to offset it.
• If the minimum prefix sum is already positive, 1 is sufficient.

This gives us a direct formula:

answer = max(1, 1 - minimumPrefix)

We only need a single pass through the array.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × k)	O(1)	Tries each possible starting value until one works
Optimal	O(n)	O(1)	Tracks minimum prefix sum in one traversal

Here, n is the length of nums, and k is the number of attempted starting values.

Algorithm Walkthrough

1. Initialize two variables:

• running_sum = 0, to track the cumulative prefix sum.
• minimum_prefix = 0, to store the smallest prefix sum encountered.

2. Traverse the array from left to right.
3. For each number:

• Add it to running_sum.

• Update minimum_prefix with the smaller of:

• the current minimum_prefix

• the current running_sum

4. After processing all elements, calculate the required starting value:

• If minimum_prefix is 0 or positive, return 1.
• Otherwise, return 1 - minimum_prefix.

5. Return the computed result.

Why it works

The algorithm works because the running total at any position equals:

startValue + prefixSum

The most dangerous moment is when the prefix sum is smallest. If we guarantee that this lowest point is still at least 1, then every other step will also be safe because their prefix sums are larger.

Therefore, choosing:

startValue = 1 - minimumPrefix

is the smallest value that prevents the running sum from ever dropping below 1.

Python Solution

from typing import List

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        running_sum = 0
        minimum_prefix = 0

        for num in nums:
            running_sum += num
            minimum_prefix = min(minimum_prefix, running_sum)

        return max(1, 1 - minimum_prefix)

The implementation closely follows the optimal algorithm.

We begin with running_sum = 0 because no numbers have been processed yet. The variable minimum_prefix also starts at 0, which represents the empty prefix before processing the array.

As we iterate through nums, each value is added to running_sum. After updating the cumulative sum, we compare it with the current minimum prefix and keep whichever is smaller.

Once the traversal finishes, we calculate the smallest valid starting value using:

max(1, 1 - minimum_prefix)

The max(1, ...) ensures the result is always positive, even when all prefix sums are non-negative.

Go Solution

func minStartValue(nums []int) int {
    runningSum := 0
    minimumPrefix := 0

    for _, num := range nums {
        runningSum += num

        if runningSum < minimumPrefix {
            minimumPrefix = runningSum
        }
    }

    result := 1 - minimumPrefix
    if result < 1 {
        return 1
    }

    return result
}

The Go implementation mirrors the Python logic almost exactly. Since Go does not have a built-in min function for integers, we use a simple conditional statement to update minimumPrefix.

There are no concerns about integer overflow because the constraints are very small. The cumulative sum is bounded by:

100 × 100 = 10,000

which easily fits within Go's integer range.

The function safely handles all valid inputs, including arrays with only positive numbers and arrays containing large negative prefixes.

Worked Examples

Example 1

Input:

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

Index	Number	Running Sum	Minimum Prefix
Start	-	0	0
0	-3	-3	-3
1	2	-1	-3
2	-3	-4	-4
3	4	0	-4
4	2	2	-4

The minimum prefix sum is -4.

Required starting value:

1 - (-4) = 5

Answer: 5

Example 2

Input:

nums = [1, 2]

Index	Number	Running Sum	Minimum Prefix
Start	-	0	0
0	1	1	0
1	2	3	0

The minimum prefix sum never goes below 0.

Required starting value:

max(1, 1 - 0) = 1

Answer: 1

Example 3

Input:

nums = [1, -2, -3]

Index	Number	Running Sum	Minimum Prefix
Start	-	0	0
0	1	1	0
1	-2	-1	-1
2	-3	-4	-4

The minimum prefix sum is -4.

Required starting value:

1 - (-4) = 5

Answer: 5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We traverse the array exactly once
Space	O(1)	Only a few variables are used

The time complexity is linear because every element is processed once during the traversal. No nested loops or repeated simulations are required.

The space complexity is constant because the algorithm only stores a running sum and the minimum prefix value, regardless of input size.

Test Cases

solution = Solution()

assert solution.minStartValue([-3, 2, -3, 4, 2]) == 5  # Example 1
assert solution.minStartValue([1, 2]) == 1  # Example 2
assert solution.minStartValue([1, -2, -3]) == 5  # Example 3

assert solution.minStartValue([5]) == 1  # Single positive element
assert solution.minStartValue([-5]) == 6  # Single negative element
assert solution.minStartValue([0]) == 1  # Single zero element

assert solution.minStartValue([1, 1, 1, 1]) == 1  # All positive numbers
assert solution.minStartValue([-1, -2, -3]) == 7  # Continuously decreasing sum
assert solution.minStartValue([2, -5, 3, -1]) == 4  # Mixed positive and negative

assert solution.minStartValue([100] * 100) == 1  # Maximum positive stress case
assert solution.minStartValue([-100] * 100) == 10001  # Maximum negative stress case

Test	Why
[-3,2,-3,4,2]	Validates the first official example
[1,2]	Ensures all-positive arrays return 1
[1,-2,-3]	Validates recovery after an early positive
[5]	Tests single positive element
[-5]	Tests single negative element
[0]	Ensures zero still requires positive start
[1,1,1,1]	Confirms no unnecessary increase in start value
[-1,-2,-3]	Tests steadily decreasing prefix sums
[2,-5,3,-1]	Tests fluctuating cumulative sums
[100] * 100	Stress case with maximum positive values
[-100] * 100	Stress case with worst negative prefix

Edge Cases

Array Contains Only Positive Numbers

If every number is positive, the running sum only increases. A common mistake is to compute a starting value larger than necessary. Since the running total can never decrease below 1, the minimum valid answer is simply 1.

For example:

nums = [2, 3, 4]

The prefix sum is always positive, so the implementation returns 1.

Large Negative Prefix Early in the Array

The most dangerous scenario often occurs near the beginning of the array, where a large negative value immediately drops the running sum.

For example:

nums = [-8, 2, 3]

A naive implementation that only checks the final sum would fail because the total eventually becomes positive. Our solution correctly tracks the minimum prefix sum, ensuring every intermediate step remains valid.

Prefix Sum Recovers Later

Sometimes the cumulative sum becomes very negative and later recovers due to positive values.

For example:

nums = [-4, -2, 10]

Even though the final cumulative sum is positive, the running total temporarily reaches -6. The implementation handles this correctly by remembering the lowest prefix sum encountered and computing the necessary starting value from that minimum point.