Description

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.

Demo walk through step by step sum

startValue = 4startValue = 5nums
(4 -3 ) = 1(5 -3 ) = 2-3
(1 +2 ) = 3(2 +2 ) = 42
(3 -3 ) = 0(4 -3 ) = 1-3
(0 +4 ) = 4(1 +4 ) = 54
(4 +2 ) = 6(5 +2 ) = 72

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] <= 100

Solution

The brute force algorithm would look like this. For each minStartValue >= 1, check if the sum of elements of nums return negative result. If yes, break out of loop else continue iterating until end of all elements of nums.

 1minStartValue = 1
 2initialize variable to keep track of sum
 3initialize variable found to keep track if we found minStartValue
 4while true
 5    sum = minStartValue
 6    found = true
 7    for i = 0; i < nums.length; i++
 8        sum += nums[i]
 9        if (sum < 1)
10            found = false
11            minStartValue++
12            break
13    if found
14        return minStartValue

 1class Solution {
 2    public int minStartValueBrute(int[] nums) {
 3        int minStartValue = 1;
 4        int sum;
 5        boolean found;
 6        while (true) {
 7            sum = minStartValue;
 8            found = true;
 9            for (int i = 0; i < nums.length; i++) {
10                sum = sum + nums[i];
11                if (sum < 1) {
12                    minStartValue++;
13                    found = false;
14                    break;
15                }
16            }
17            if (found) {
18                return minStartValue;
19            }
20        }
21    }
22}

Prefix Sum - Preprocessing

In this case, we are looking for a positive number, which if added to all other numbers, will result in positive value. If we look carefully at the operation we performed on array with input [-3,2,-3,4,2], we started with 5 and added each number of the input array. Thus we need to find the minimum value of prefix sum array and we want one greater than that value, this will be 1 - minSum. This is applicable only if 1 - minSum >= 1. That is if minSum < 1. If minSum >= 1 then we can simply use 1 as the lowest value because in this case, the sum is never going below 1.

 1class Solution {
 2    public int minStartValue(int[] nums) {
 3        int[] prefixSum = new int[nums.length];
 4        prefixSum[0] = nums[0];
 5        int minSum = prefixSum[0];
 6
 7        for (int i = 1; i < nums.length; ++i) {
 8            prefixSum[i] += prefixSum[i - 1] + nums[i];
 9            minSum = Math.min(minSum, prefixSum[i]);
10        }
11        return minSum >= 0 ? 1 : 1 - minSum;
12    }
13}

There is little improvement we can make if we modify nums in place to store prefix sum. This original array is no longer used, so it can be modified in-place to save memory.

 1class Solution {
 2    public int minStartValue(int[] nums) {
 3        int minSum = nums[0];
 4
 5        for (int i = 1; i < nums.length; ++i) {
 6            nums[i] = nums[i - 1] + nums[i];
 7            minSum = Math.min(minSum, nums[i]);
 8        }
 9        return minSum >= 0 ? 1 : 1 - minSum;
10    }
11}