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 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 = 5 | nums (4 -3 ) = 1 | (5 -3 ) = 2 | -3 (1 +2 ) = 3 | (2 +2 ) = 4 | 2 (3 -3 ) = 0 | (4 -3 ) = 1 | -3 (0 +4 ) = 4 | (1 +4 ) = 5 | 4 (4 +2 ) = 6 | (5 +2 ) = 7 | 2
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] <= 100The idea is to simulate the step by step summation of the start value with the elements of the array. We maintain a running sum and adjust the start value such that this sum never drops below 1. At each step, if the running sum is less than 1, we calculate and update the new minimum start value needed to keep the running sum at least 1.
We iterate over the nums array, maintaining a cumulative running sum. We track the minimum value of this sum as min_sum. After processing all elements, the start value must be greater than or equal to 1 minus this minimum sum in order to ensure the step by step sum never falls below 1.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), as we are using a constant amount of space.
This approach is similar to the first but conceptualized through using prefix sums and adjusting the needed start value based on the lowest prefix sum reached. We cumulatively add each number and check if the prefix sum dips below a certain threshold, indicating the minimal adjustment needed for the start value.
By maintaining a prefix sum across the array, the minimum observed prefix sum is used to calculate the requisite start value. This ensures the prefix sum stays positive throughout iterations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Calculate Minimum Start Value using Cumulative Sum | Time Complexity: O(n), where n is the length of nums. |
| Prefix Sum with Constant Adjustment | Time Complexity: O(n). |
Minimum Value to Get Positive Step by Step Sum | Leetcode 1413 | Live coding session 🔥🔥🔥 • Coding Decoded • 3,374 views views
Watch 9 more video solutions →Practice Minimum Value to Get Positive Step by Step Sum with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor