Lowest Safe Starting Value for a Running Sum
Updated
Problem statement
You are given an integer array nums. Pick a positive integer start. A running sum begins at start, and you walk through nums in order, adding each number to it.
Each time a number is added, the new total has to be 1 or more. Find the least positive start for which no total ever drops under 1.
Function
minStartValue(nums: int[]) → intExamples
Example 1
nums = [2,-5,1,-3]return = 6With start = 6 the running sums are 8, 3, 4 and 1, all at least 1. With start = 5 the last one would be 0, so 6 is the smallest.
Example 2
nums = [4,1,7]return = 1All three numbers are above zero, so the totals only grow. The start still has to be positive, so the answer is 1.
Example 3
nums = [-1,-1,10,-12]return = 5With start = 5 the running sums are 4, 3, 13 and 1. The lowest point comes at the very end, right after the highest one. A start of 4 would end at 0.
Constraints
1 <= nums.length <= 10^4-2 * 10^5 <= nums[i] <= 2 * 10^5
More OpenAI Online Assessment questions
- Count Routes Through Four Shop TypesOA · Seen Oct 2026
- Digit-Sum Sequence Join PointOA · Seen Oct 2026
- Network Endpoint or Cycle BoundaryOA · PHONE SCREEN · Seen Oct 2026
- Password Clues and the Next CommandOA · Seen Oct 2026
- Longest Increasing Price SubsequenceOA · Seen Oct 2026
- Macaron Order PriceOA · Seen Oct 2026
- Shortest Atom Action PathOA · Seen Oct 2026
- Simplify a Quadratic ExpressionOA · Seen Oct 2026
- Minimum-Cost Color SequenceOA · PHONE SCREEN · Seen Oct 2026
- Largest Microorganism After ConsumptionOA · Seen Oct 2026
Similar questions at other companies
- Minimum Positive Starting ValueBooking.com · OA
- Array Interval SumsHeadlands Technologies · OAHeadlands Technologies interview questions
- Minimum AmountBelvedere Trading · OA
- Online No-Intercept Linear RegressionTwo Sigma · OATwo Sigma interview questions
- Range Sum QueriesIntuit · OAIntuit interview questions
- Shortest Distance on a Circular Bus RouteAmazon · OA
- Count Sortable SplitsGoogle · OAGoogle interview questions
- Array Challenge (QR Intern)Akuna Capital · OAAkuna Capital interview questions
- Range Negation UpdatesJP Morgan Chase · OAJP Morgan Chase interview questions
- Threshold AlertsGoldman Sachs · OAGoldman Sachs interview questions