Minimum Value to Get Positive Step by Step Sum

Easy Arrays & Hashing Prefix Sum Strategy Original on LeetCode

Reported atSwiggy

Minimum Value to Get Positive Step by Step Sum is a easy arrays & hashing problem solved with the prefix sum strategy pattern. The best approach, optimal (minimum prefix sum), runs in O(n) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try start values one by one) up.

Problem

You are given an integer array nums. Pick a positive integer startValue, then add the elements of nums to it one at a time, from left to right, keeping a running total.

Return the smallest positive startValue for which the running total never drops below 1 at any step.

Examples

Example 1

Input
nums = [-4, 2, -3, 1]
Output
6
Why
Starting at 6 the running totals are 2, 4, 1, 2, all at least 1. Starting at 5 the third total would be 0.

Example 2

Input
nums = [3, 1, 2]
Output
1
Why
Every number is positive, so the smallest allowed start, 1, already works.

Example 3

Input
nums = [2, -5, 4]
Output
4
Why
The prefix sums are 2, -3, 1. The lowest is -3, so the start must be at least 1 - (-3) = 4.

Constraints

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try start values one by one)O(n · S)O(1)
Optimal (minimum prefix sum)O(n)O(1)

1Brute force (try start values one by one)

TimeO(n · S)Each candidate costs up to n steps, and the answer S can be as large as 1 + 100 * n.
SpaceO(1)Only a running total.

Try startValue = 1, 2, 3, .... For each candidate, add the numbers one by one and stop as soon as the running total drops below 1. The first candidate that survives the whole array is the answer.

  1. For start = 1, 2, 3, ...:
  2. Set total = start and add each nums[i]; if total < 1 at any point, this start fails.
  3. Return the first start that never fails.
class Solution {
    public int minStartValue(int[] nums) {
        for (int start = 1; ; start++) {
            int total = start;
            boolean ok = true;
            for (int x : nums) {
                total += x;
                if (total < 1) {
                    ok = false;
                    break;
                }
            }
            if (ok) return start;
        }
    }
}

2Optimal (minimum prefix sum)

TimeO(n)One pass over the array.
SpaceO(1)Two integers.

After step i the total is startValue + prefix[i]. All of these are at least 1 exactly when startValue >= 1 - minPrefix, where minPrefix is the smallest prefix sum. The start must also be positive, so the answer is max(1, 1 - minPrefix).

  1. Walk the array keeping a running prefix sum and the smallest value it reaches.
  2. Return max(1, 1 - minPrefix).
class Solution {
    public int minStartValue(int[] nums) {
        int prefix = 0, minPrefix = 0;
        for (int x : nums) {
            prefix += x;
            minPrefix = Math.min(minPrefix, prefix);
        }
        return 1 - minPrefix;
    }
}

Edge cases to test

  • All numbers positive: the answer is 1
  • A single negative number
  • The lowest running total comes at the very end
  • Every number is -100, so the answer reaches 1 + 100 * n

Hints

Hint 1

Write the running total after step i as startValue + prefix[i]. What does each step require?

Hint 2

Every step needs startValue + prefix[i] >= 1, so only the smallest prefix sum matters.

FAQ

What is the best time complexity for Minimum Value to Get Positive Step by Step Sum?

Optimal (minimum prefix sum) runs in O(n) time and O(1) extra space. One pass over the array.

Which pattern does Minimum Value to Get Positive Step by Step Sum use?

It is a arrays & hashing problem that uses the prefix sum strategy pattern. Other problems with the same pattern: Subarray Sum Equals K, Subarray with given XOR, Range Sum Query - Immutable.

Is there a brute force solution for Minimum Value to Get Positive Step by Step Sum?

Yes. Brute force (try start values one by one) takes O(n · S) time and O(1) space. Try startValue = 1, 2, 3, ....

Which edge cases should I test for Minimum Value to Get Positive Step by Step Sum?

All numbers positive: the answer is 1; A single negative number; The lowest running total comes at the very end; Every number is -100, so the answer reaches 1 + 100 n.