Code Logo

Minimum Value to Get Positive Step by Step Sum

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Minimum Value to Get Positive Step by Step Sum

Solution Approach

Compute prefix sums tracking the minimum sum. Answer = 1 - minSum.

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

Time O(n), Space 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;
    }
}