problemeasyalgorithmsleetcode-1413leetcode 1413leetcode1413

Minimum Value to Get Positive Step by Step Sum

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

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

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

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

C++
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;
    }
};
Go
func MinStartValue(nums []int) int {
    sum, minSum := 0, 0
    for _, x := range nums {
        sum += x
        if sum < minSum {
            minSum = sum
        }
    }
    return 1 - minSum
}
Java
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;
    }
}
Kotlin
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
    }
}
Python
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
Rust
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
    }
}
TypeScript
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.

Comments