Code Implementation

class Solution:
    def minStartValue(self, nums):
        min_sum = 0
        curr_sum = 0
        for num in nums:
            curr_sum += num
            min_sum = min(min_sum, curr_sum)
        return 1 - min_sum
      

class Solution {
public:
    int minStartValue(vector<int>& nums) {
        int min_sum = 0;
        int curr_sum = 0;
        for (int num : nums) {
            curr_sum += num;
            min_sum = min(min_sum, curr_sum);
        }
        return 1 - min_sum;
    }
};
      

class Solution {
    public int minStartValue(int[] nums) {
        int minSum = 0;
        int currSum = 0;
        for (int num : nums) {
            currSum += num;
            minSum = Math.min(minSum, currSum);
        }
        return 1 - minSum;
    }
}
      

var minStartValue = function(nums) {
    let minSum = 0;
    let currSum = 0;
    for (let num of nums) {
        currSum += num;
        minSum = Math.min(minSum, currSum);
    }
    return 1 - minSum;
};
      

Problem Description

You are given an integer array nums. Your task is to find the minimum positive integer startValue such that when you initialize a variable sum = startValue and add each element of nums to sum in order, the value of sum is always greater than or equal to 1 at every step.

In other words, for each index i (from 0 to nums.length - 1), the running sum startValue + nums[0] + ... + nums[i] should never be less than 1.

• There is always exactly one valid solution.
• Elements of nums may be negative, zero, or positive.
• Do not reuse or rearrange elements; process nums in order.

Thought Process

The first instinct might be to try every possible startValue from 1 upwards, checking if the running sum ever drops below 1. However, this brute-force approach is inefficient, especially for large arrays or large negative numbers.

Instead, let's think about the problem differently: the only way the running sum can become invalid is if, at some step, the cumulative sum (starting from startValue) goes below 1. So, if we can find the lowest point the running sum ever reaches (when starting from 0), we can set startValue just high enough to keep the sum always at least 1.

In other words, we want the minimum startValue so that startValue + min_prefix_sum >= 1, where min_prefix_sum is the minimum value of the cumulative sum of nums as we iterate through the array.

Solution Approach

• Step 1: Initialize two variables: curr_sum (current cumulative sum) set to 0, and min_sum (minimum prefix sum) set to 0.
• Step 2: Iterate through each number in nums:
  • Add the current number to curr_sum.
  • Update min_sum to be the minimum of itself and curr_sum.
• Step 3: After the loop, the smallest running sum encountered is min_sum.
• Step 4: To keep every running sum at least 1, we need startValue + min_sum >= 1. So, startValue = 1 - min_sum.
• Step 5: Return 1 - min_sum as the answer.

This approach only requires a single pass through the array, making it efficient and simple to implement. No extra data structures are needed.

Example Walkthrough

Let's use the example nums = [-3, 2, -3, 4, 2].

• Start with curr_sum = 0, min_sum = 0.
• Step 1: Add -3 ⇒ curr_sum = -3, min_sum = -3
• Step 2: Add 2 ⇒ curr_sum = -1, min_sum = -3
• Step 3: Add -3 ⇒ curr_sum = -4, min_sum = -4
• Step 4: Add 4 ⇒ curr_sum = 0, min_sum = -4
• Step 5: Add 2 ⇒ curr_sum = 2, min_sum = -4

The lowest the running sum ever gets is -4. To ensure the running sum is always at least 1, we need startValue such that startValue + (-4) >= 1, so startValue >= 5.

Therefore, the answer is 5.

Time and Space Complexity

• Brute-force approach: For each possible startValue (potentially up to sum of absolute values in nums), you check the array, leading to O(N * K) time, where K is the value needed to reach a valid startValue.
• Optimized approach (the one above): Only a single pass through the array is required, so time complexity is O(N), where N is the length of nums.
• Space complexity: Both approaches only use a constant number of variables, so O(1) space.

Summary

The key insight is to track the minimum running sum as you iterate through the array. By ensuring the startValue offsets the lowest dip in the prefix sum, you can guarantee that the running sum never drops below 1. This simple, efficient approach avoids brute-force checks and works in a single pass with constant space, making the solution both elegant and practical.