Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3

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

Example 3

1
2

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

Constraints

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

Solution

Method 1 – Prefix Sum Tracking

Intuition

To keep the running sum always positive, we need to ensure that the minimum prefix sum (including the start value) is at least 1. By tracking the lowest prefix sum, we can compute the minimum start value needed.

Approach

  1. Initialize a variable to track the running sum and the minimum prefix sum.
  2. Iterate through the array, updating the running sum and minimum prefix sum.
  3. The answer is 1 - min_prefix_sum (if min_prefix_sum < 0), otherwise 1.
  4. Return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int sum = 0, min_sum = 0;
        for (int x : nums) {
            sum += x;
            min_sum = min(min_sum, sum);
        }
        return 1 - min_sum;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func MinStartValue(nums []int) int {
    sum, minSum := 0, 0
    for _, x := range nums {
        sum += x
        if sum < minSum {
            minSum = sum
        }
    }
    return 1 - minSum
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minStartValue(int[] nums) {
        int sum = 0, minSum = 0;
        for (int x : nums) {
            sum += x;
            minSum = Math.min(minSum, sum);
        }
        return 1 - minSum;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun minStartValue(nums: IntArray): Int {
        var sum = 0
        var minSum = 0
        for (x in nums) {
            sum += x
            minSum = minOf(minSum, sum)
        }
        return 1 - minSum
    }
}
1
2
3
4
5
6
7
8
9

from typing import List
class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        total = 0
        min_sum = 0
        for x in nums:
            total += x
            min_sum = min(min_sum, total)
        return 1 - min_sum
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

impl Solution {
    pub fn min_start_value(nums: Vec<i32>) -> i32 {
        let mut sum = 0;
        let mut min_sum = 0;
        for x in nums {
            sum += x;
            min_sum = min_sum.min(sum);
        }
        1 - min_sum
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    minStartValue(nums: number[]): number {
        let sum = 0, minSum = 0;
        for (const x of nums) {
            sum += x;
            minSum = Math.min(minSum, sum);
        }
        return 1 - minSum;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once to compute the prefix sums.
  • 🧺 Space complexity: O(1) — Only a few variables are used for computation.