Minimum Value to Get Positive Step by Step Sum

Easy

#1307Time: O(S * N), where N is the number of elements in `nums` and S is the final answer (the minimum start value). In the worst-case scenario (e.g., an array full of large negative numbers), S can be large, making the algorithm slow.Space: O(1), as it only uses a few variables to store the `startValue`, the running total, and a flag. The space used does not depend on the size of the input array.1 company

Patterns

Prefix Sum

Data structures

Array

Companies

Swiggy

Prompt

Given an array of integers nums, you start with an initial positive value startValue.

In each iteration, you calculate the step by step sum of startValue plus elements in nums (from left to right).

Return the minimum positive value of startValue such that the step by step sum is never less than 1.

Example 1:

Input: nums = [-3,2,-3,4,2]
Output: 5
Explanation: If you choose startValue = 4, in the third iteration your step by step sum is less than 1.
step by step sum
startValue = 4 | startValue = 5 | nums
  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

Example 2:

Input: nums = [1,2]
Output: 1
Explanation: Minimum start value should be positive.

Example 3:

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

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We start by trying the smallest possible positive startValue, which is 1. We then check if it's valid by calculating the step-by-step sum. If at any point the sum drops below 1, we know this startValue is too small, so we increment it by 1 and try again. We repeat this process until we find the first startValue for which the step-by-step sum always remains 1 or greater.

Algorithm

Initialize startValue to 1.
Start an infinite loop.
Inside the loop, create a variable currentSum and set it to startValue.
Create a boolean flag isValid and set it to true.
Iterate through the nums array. For each number:
- Add the number to currentSum.
- If currentSum becomes less than 1, it means the current startValue is not valid. Set isValid to false and break the inner loop.
After the inner loop, if isValid is still true, it means we have found the minimum positive startValue. Return the current startValue.
If isValid is false, increment startValue by 1 and continue the outer loop to test the next value.

Walkthrough

The brute-force method systematically checks every possible positive integer for startValue, beginning with 1. For each candidate startValue, it simulates the entire process of accumulating sums. A running total, initialized with the candidate startValue, is updated by adding each element of the nums array in order. During this simulation, if the running total ever falls below 1, the candidate startValue is deemed invalid. The simulation for that candidate stops, and the algorithm proceeds to the next integer (startValue + 1). The first startValue that allows the simulation to complete without the sum ever dropping below 1 is guaranteed to be the minimum positive startValue required, and it is returned as the result.

1class Solution {2    public int minStartValue(int[] nums) {3        int startValue = 1;4        while (true) {5            int total = startValue;6            boolean isValid = true;7            for (int num : nums) {8                total += num;9                if (total < 1) {10                    isValid = false;11                    break;12                }13            }14            if (isValid) {15                return startValue;16            }17            startValue++;18        }19    }20}

Complexity

Time

O(S * N), where N is the number of elements in `nums` and S is the final answer (the minimum start value). In the worst-case scenario (e.g., an array full of large negative numbers), S can be large, making the algorithm slow.

Space

O(1), as it only uses a few variables to store the `startValue`, the running total, and a flag. The space used does not depend on the size of the input array.

Trade-offs

Pros

The logic is straightforward and easy to understand as it directly models the problem statement.
It requires minimal extra memory.

Cons

This approach can be slow if the required startValue is large, as it involves nested loops.
It performs redundant calculations by repeatedly summing up parts of the array.

A more efficient method is to analyze the condition mathematically. The requirement is that startValue plus any prefix sum of nums must be at least 1. This implies that startValue must be large enough to prevent even the most negative step-by-step sum from dropping below 1. By finding the minimum prefix sum that occurs, we can directly calculate the minimum startValue needed to satisfy the condition in a single pass.

Algorithm

Initialize two integer variables: total to 0 (to keep track of the running sum) and minVal to 0 (to keep track of the minimum running sum encountered).
Iterate through each number num in the nums array.
In each iteration, add num to total.
Update minVal to be the minimum of its current value and the new total (i.e., minVal = min(minVal, total)).
After the loop finishes, minVal will hold the minimum prefix sum. If all prefix sums were positive, minVal will be 0.
The condition to satisfy is startValue + minVal >= 1.
To find the minimum startValue, we solve for it: startValue >= 1 - minVal.
The smallest integer startValue is therefore 1 - minVal. Return this value.

Walkthrough

This approach is based on a key insight. Let the step-by-step sum after considering i elements be Sum_i = startValue + nums[0] + ... + nums[i-1]. The condition is Sum_i >= 1 for all i. This is equivalent to startValue + prefixSum[i-1] >= 1, where prefixSum is the sum of elements from nums. For this inequality to hold for all i, it must hold for the minimum possible prefix sum. Let minPrefixSum be the minimum value among all prefix sums. The condition simplifies to startValue + minPrefixSum >= 1. Solving for startValue, we get startValue >= 1 - minPrefixSum. Since we need the minimum positive startValue, we can find the minPrefixSum by iterating through the array once. We maintain a running sum and a variable to track the minimum sum seen so far. The final answer is then 1 - minPrefixSum.

1class Solution {2    public int minStartValue(int[] nums) {3        int minVal = 0;4        int total = 0;5        for (int num : nums) {6            total += num;7            minVal = Math.min(minVal, total);8        }9        // The minimum startValue should be such that:10        // startValue + minVal >= 111        // startValue >= 1 - minVal12        return 1 - minVal;13    }14}

Complexity

Time

O(N), where N is the number of elements in `nums`. This is because we only need to iterate through the array once to find the minimum prefix sum.

Space

O(1), as it only uses a couple of variables to store the running total and the minimum value, regardless of the input size.

Trade-offs

Pros

Extremely efficient, solving the problem in a single pass through the input array.
Optimal time and space complexity.

Cons

The logic is less direct than the brute-force approach and requires a small mathematical insight to understand why it works.

Solutions

Solution

1class Solution {2public3  int minStartValue(int[] nums) {4    int s = 0;5    int t = Integer.MAX_VALUE;6    for (int num : nums) {7      s += num;8      t = Math.min(t, s);9    }10    return Math.max(1, 1 - t);11  }12}

1class Solution {2public:3  int minStartValue(vector<int> &nums) {4    int s = 0, t = INT_MAX;5    for (int num : nums) {6      s += num;7      t = min(t, s);8    }9    return max(1, 1 - t);10  }11};

1class Solution : def minStartValue ( self , nums : List [ int ]) -> int : s , t = 0 , inf for num in nums : s += num t = min ( t , s ) return max ( 1 , 1 - t )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem