Minimum Value to Get Positive Step by Step Sum

Difficulty: Easy | Acceptance: 64.70% | Paid: No Topics: Array, Prefix Sum

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
• Constraints
• Approach 1: Simulation
• Approach 2: Prefix Sum

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 + nums[0] = 1
startValue = 4 | startValue + nums[0] + nums[1] = 3
startValue = 4 | startValue + nums[0] + nums[1] + nums[2] = 0
startValue = 4 | startValue + nums[0] + nums[1] + nums[2] + nums[3] = 4
startValue = 4 | startValue + nums[0] + nums[1] + nums[2] + nums[3] + nums[4] = 6

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

Approach 1: Simulation

Intuition We can simulate the process by trying start values starting from 1. For each candidate start value, we calculate the running sum. If the running sum drops below 1 at any point, we increment the start value and try again.

Steps

• Initialize startValue to 1.
• Enter a loop that continues indefinitely.
• Inside the loop, initialize total to the current startValue.
• Iterate through the nums array, adding each number to total.
• If total becomes less than 1, break the inner loop and increment startValue.
• If the inner loop completes successfully, return the current startValue.

class Solution:
    def minStartValue(self, nums: list[int]) -> int:
        startValue = 1
        while True:
            total = startValue
            valid = True
            for n in nums:
                total += n
                if total < 1:
                    valid = False
                    break
            if valid:
                return startValue
            startValue += 1

Complexity

• Time: O(N * M), where N is the length of the array and M is the value of the result. In the worst case, this can be slow.
• Space: O(1)
• Notes: This approach is intuitive but inefficient for large inputs or large negative numbers.

Approach 2: Prefix Sum

Intuition Instead of simulating, we can determine the minimum start value mathematically. We need startValue + prefixSum[i] >= 1 for all indices i. This implies startValue >= 1 - prefixSum[i]. To satisfy this for all steps, startValue must be at least 1 - minPrefixSum. Since startValue must be positive, we take the maximum of 1 and this calculated value.

Steps

• Initialize minSum to 0 and currentSum to 0.
• Iterate through the nums array.
• Add the current number to currentSum.
• Update minSum to be the minimum of minSum and currentSum.
• After the loop, calculate the required start value as max(1, 1 - minSum).

class Solution:
    def minStartValue(self, nums: list[int]) -> int:
        min_sum = 0
        curr = 0
        for n in nums:
            curr += n
            min_sum = min(min_sum, curr)
        return max(1, 1 - min_sum)

Complexity

• Time: O(N), where N is the length of the array. We pass through the array once.
• Space: O(1), we only use a few variables for tracking sums.
• Notes: This is the optimal solution for this problem.