Minimum Value to Get Positive Step by Step Sum

return smallest start values such that adding all the values in array are always positive

Minimum Value to Get Positive Step by Step Sum

Problem

You are given an array of integers nums. You choose a positive integer startValue.

We add the numbers of nums one by one from left to right, starting from startValue. This gives a step by step sum.

Return the minimum positive 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

• With startValue = 4, the sums are 1, 3, 0, 4, 6. The third sum is 0, which is less than 1. So 4 does not work.
• With startValue = 5, the sums are 2, 4, 1, 5, 7. All sums are at least 1. So 5 works.

Example 2

Input: nums = [1,2]
Output: 1

• The start value must be positive, so the smallest choice is 1.
• The sums are 2, 4. All are at least 1.

Example 3

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

• With startValue = 5, the sums are 6, 4, 1. All are at least 1.
• With startValue = 4, the last sum is 0. So 4 does not work.

Constraints

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

Main Idea

We use prefix sums. A prefix sum is the sum of the numbers from the start up to the current index.

• The step by step sum at index i is startValue + prefix[i].
• The hardest step is the one with the smallest prefix sum. Let us call it minimal.
• If the hardest step is at least 1, every other step is also at least 1.
• So we need: startValue + minimal >= 1.
• This gives: startValue >= 1 - minimal.

Now there are two cases:

• minimal > 0: Every prefix sum is already positive. We can use the smallest positive value, which is 1.
• minimal <= 0: We must lift the smallest sum up to 1. The answer is 1 - minimal, which is 1 + Math.abs(minimal).

Solution 1: Prefix Sum Array

var minStartValue = function (nums) {
    let temp = [];
    let tempsum = 0;

    // build the prefix sums
    for (let i = 0; i < nums.length; i++) {
        temp.push(nums[i] + tempsum);
        tempsum += nums[i];
    }

    // the smallest prefix sum is the hardest step
    let minimal = Math.min(...temp);

    // all prefix sums are positive
    if (minimal > 0) {
        return 1;
    }

    // lift the smallest sum up to 1
    return 1 + Math.abs(minimal);
};

How the Code Works

• Step 1: temp stores the prefix sums. tempsum is the running total.
• Step 2: In each loop step, we push nums[i] + tempsum, which is the prefix sum at i. Then we add nums[i] to tempsum.
• Step 3: Math.min(...temp) finds the smallest prefix sum.
• Step 4: If it is positive, we return 1. If not, we return 1 + Math.abs(minimal).

Dry Run

Let us take nums = [-3, 2, -3, 4, 2].

• The smallest prefix sum is -4.
• The answer is 1 + 4 = 5.

Now let us take nums = [1, 2].

• The prefix sums are 1, 3.
• The smallest is 1, which is greater than 0. So the answer is 1.

Complexity

• Time Complexity: O(n)
  • n is the length of the array.
  • One loop builds the prefix sums, and Math.min scans them once.
• Space Complexity: O(n)
  • The temp array stores n prefix sums.

Tip: Math.min(...temp) can fail for very large arrays. Here n <= 100, so it is safe.

Solution 2: Running Sum (O(1) Space)

We do not need to store all prefix sums. We only need the smallest one. So we keep a running sum and a minimal value.

var minStartValue = function (nums) {
    let sum = 0;
    let minimal = 0;

    for (let num of nums) {
        sum += num;
        minimal = Math.min(minimal, sum);
    }

    return 1 - minimal;
};

How the Code Works

• sum is the current prefix sum.
• minimal starts at 0. It keeps the smallest prefix sum seen so far.
• If all prefix sums are positive, minimal stays 0, and the answer is 1 - 0 = 1.
• If some prefix sum is negative, minimal is that negative number, and the answer is 1 - minimal.
• Starting minimal at 0 handles both cases in one line, so we do not need an if.

Complexity

• Time Complexity: O(n)
  • We go through the array once.
• Space Complexity: O(1)
  • We use only two variables.

Comparison

Summary

• The step by step sum at each index is startValue + prefix sum.
• Only the smallest prefix sum matters, because it is the hardest step.
• We need startValue + minimal >= 1, so the answer is 1 - minimal.
• If the smallest prefix sum is positive, the answer is 1.
• The running sum version uses minimal = 0 at the start, so both cases are handled together.
• Both solutions run in O(n) time. The running sum version uses only O(1) space.