Code Logo

Minimum Value to Get Positive Step by Step Sum

Published at24 Jul 2026
Created by
Easy 1 views
Like0

Given an array of integers nums, you start with an initial positive value startValue. In each iteration you add nums[i] to your current value. Find the minimum positive startValue such that the running sum never drops below 1.

The running sum at index i is startValue + sum(nums[0..i]). For this to never drop below 1, startValue must be at least 1 - minPrefix, where minPrefix is the minimum prefix sum. Since startValue must be positive, the answer is max(1, 1 - minPrefix).

This is solved by computing prefix sums of nums, tracking the minimum value encountered, then returning the required start value. Time O(n), Space O(1).

Edge cases include all positive nums (startValue = 1), empty array (return 1), and large negative values.

The running sum computation is a simple DP prefix sum. By tracking the minimum prefix value, we determine the required starting offset to keep all prefix sums above zero. This technique is used in financial projections and cumulative cost analysis.

The minimum prefix sum represents the greatest cumulative deficit encountered. By setting startValue to 1 minus this deficit, we guarantee the running sum never falls below 1. This is a direct application of the prefix sum DP pattern where we maintain a running total and track its extremum.

Example Input & Output

Example 1
Input
[1,-2,-3]
Output
5
Explanation

Min prefix = -4, start = 5.

Example 2
Input
[-3,2,-3,4,2]
Output
5
Explanation

Min prefix sum = -4, start = 1-(-4)=5.

Example 3
Input
[-5]
Output
6
Explanation

Only -5, start = 1-(-5)=6.

Example 4
Input
[0,0,0]
Output
1
Explanation

Zeros, start = 1.

Example 5
Input
[1,2]
Output
1
Explanation

All positive, start = 1.

Algorithm Flow

Recommendation Algorithm Flow for Minimum Value to Get Positive Step by Step Sum

Solution Approach

Given an array of integers nums, start with an initial value and add each number sequentially. Find the minimum initial value such that the running sum never drops below 1. Track the running sum and the minimum running sum encountered. The minimum starting value is max(1, 1 - minSum).

function minStartValue(nums) {
  var sum = 0, minSum = 0;
  for (var i = 0; i < nums.length; i++) {
    sum += nums[i];
    if (sum < minSum) minSum = sum;
  }
  return 1 - minSum;
}

The running sum starts at the initial value and changes with each element. The minimum running sum tells us the largest negative dip. To keep all running sums >= 1, the starting value must offset this dip by at least 1 - minSum. If the dip is positive (or zero), start at 1.

Time complexity is O(n), space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int[] nums) {
        int min = 0, sum = 0;
        for (int n : nums) {
            sum += n;
            if (sum < min) min = sum;
        }
        return 1 - min;
    }
}