Minimum Value To Get Positive Step By Step Sum - Leetcode Solution

Problem Statement:

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.

Example:

Input: nums = [-3,2,-1,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 = 5 | nums (4 -3 ) = 1 | (5 -3 ) = 2 | -3 (1 +2 ) = 3 | (2 +2 ) = 4 | 2 (3 -1 ) = 2 | (4 -1 ) = 3 | -1 (2 +4 ) = 6 | (3 +4 ) = 7 | 4 (6 -2 ) = 4 | (7 -2 ) = 5 | -2

Solution:

To get a detailed understanding of this solution, we'll divide it into simple steps:

Step 1: Initialize startValue with 1 and stepByStepSum with 0. Step 2: Traverse the array and add each element to the start value and calculate the step by step sum. Step 3: If at any point the step by step sum becomes less than 1, we'll reset the start value to the minimum positive integer required to make the step by step sum positive again from that point. Step 4: Return the final start value after traversing the entire array.

Python Code:

class Solution: def minStartValue(self, nums: List[int]) -> int:

    # Initializing startValue with 1 and stepByStepSum with 0
    startValue = 1
    stepByStepSum = 0
    
    # Traversing the array and calculating the step by step sum
    for num in nums:
        stepByStepSum += num
        if stepByStepSum < 1:
            # Resetting the start value to minimum positive integer
            startValue += 1 - stepByStepSum
            stepByStepSum = 1
            
    # Returning the final start value
    return startValue

Time Complexity: O(n) where n is the length of input array nums. Space Complexity: O(1) as we are not using any extra space.

1