Minimum Value to Get Positive Step by Step Sum
Problem
Given an array nums, choose a positive integer startValue such that the running sum startValue + nums[0] + nums[1] + … is never less than 1 at any step. Return the minimum such startValue.
nums = [-3, 2, -3, 4, 2]5def min_start_value(nums):
s = 0
mn = 0
for x in nums:
s += x
if s < mn:
mn = s
return 1 - mnfunction minStartValue(nums) {
let s = 0, mn = 0;
for (const x of nums) {
s += x;
if (s < mn) mn = s;
}
return 1 - mn;
}class Solution {
public int minStartValue(int[] nums) {
int s = 0, mn = 0;
for (int x : nums) {
s += x;
if (s < mn) mn = s;
}
return 1 - mn;
}
}int minStartValue(vector<int>& nums) {
int s = 0, mn = 0;
for (int x : nums) {
s += x;
if (s < mn) mn = s;
}
return 1 - mn;
}Explanation
The whole problem hinges on one observation: whatever startValue we choose, it gets added to every running total equally. So the running sum is at its lowest exactly where the plain prefix sum of nums is at its lowest. Fix that worst point and everything else is automatically fine.
So we walk through nums keeping a running prefix sum s, and track mn, the minimum prefix sum seen so far (starting at 0 to cover the empty prefix before any element).
We want that lowest point, once startValue is added, to land on exactly 1 (the smallest allowed value). That means startValue + mn = 1, so the answer is 1 - mn.
Example: nums = [-3, 2, -3, 4, 2] gives prefix sums -3, -1, -4, 0, 2. The minimum is -4, so startValue = 1 - (-4) = 5, which keeps every step at least 1.