Smallest Start for a Positive Walk
Problem
You pick a positive whole number as a starting value, then add the numbers of a list to it one at a time, from left to right. Return the smallest starting value for which the running total never drops below 1 at any step.
Examples
Input: nums = [-3, 2, -3, 4, 2]
Output: 5
Why: 5 goes to 2, 4, 1, 5, 7, while 4 would reach 0 after the third stepInput: nums = [1, 2]
Output: 1
Why: the total only grows, so the smallest positive start worksInput: nums = [1, -2, -3]
Output: 5
Why: edge case, the lowest point comes at the very endHints
0 / 3
Trying start values one by one works but repeats the whole walk each time. What single fact about the list decides the answer?
The start is added to every running total, so only the lowest running total matters. It must be lifted to at least 1.
Walk the list once, keeping the running sum and the lowest value it has reached, starting from 0 so the walk before any step counts too. The answer is 1 minus that lowest value.
Solution
This is the fuel tank from the gas station lesson: the running sum is the tank, and a start value is fuel you bring along. Adding a start value s lifts every running total by exactly s, so the walk stays at 1 or above precisely when s plus the lowest running total is at least 1. One pass finds that lowest total. Starting the minimum at 0 covers lists whose running sum never goes negative, where the answer is the smallest positive start, 1. Time is O(n) and space is O(1).
def smallest_start(nums):
total = lowest = 0
for x in nums:
total += x
lowest = min(lowest, total) # the deepest dip of the running sum
return 1 - lowest # lowest <= 0, so this is at least 1
print(smallest_start([-3, 2, -3, 4, 2])) # -> 5
print(smallest_start([1, 2])) # -> 1
print(smallest_start([1, -2, -3])) # -> 5Stuck on the idea rather than the code? Gas Station covers it.