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.
step by step sum
startValue = 4 | startValue = 5 | nums
(4 -3 ) = 1 | (5 -3 ) = 2 | -3
(1 +2 ) = 3 | (2 +2 ) = 4 | 2
(3 -3 ) = 0 | (4 -3 ) = 1 | -3
(0 +4 ) = 4 | (1 +4 ) = 5 | 4
(4 +2 ) = 6 | (5 +2 ) = 7 | 2
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:
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode.AskGif.Easy.Array
{
public class MinStartValueSoln
{
public int MinStartValue(int[] nums)
{
if(nums.Length == 0)
{
return 0;
}
int minVal = 0;
int sum = 0;
for (int i = 0; i < nums.Length; i++)
{
sum += nums[i];
if (sum < 0 && (Math.Abs(sum) + 1 > minVal))
{
minVal = Math.Abs(sum)+ 1;
}
}
if(minVal == 0)
{
minVal = 1;
}
return minVal;
}
}
}
Time Complexity: O(n)
Space Complexity: O(1)
Unit Tests:
using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;
namespace CodingUnitTest.Easy.Array
{
[TestClass]
public class MinStartValueSolnTests
{
[TestMethod]
public void MinStartValueSoln_First()
{
var input = new int[] { -3, 2, -3, 4, 2 };
var output = 5;
var res = new MinStartValueSoln().MinStartValue(input);
Assert.AreEqual(res, output);
}
[TestMethod]
public void MinStartValueSoln_Second()
{
var input = new int[] { 1, 2 };
var output = 1;
var res = new MinStartValueSoln().MinStartValue(input);
Assert.AreEqual(res, output);
}
[TestMethod]
public void MinStartValueSoln_Third()
{
var input = new int[] { 1, -2, -3 };
var output = 5;
var res = new MinStartValueSoln().MinStartValue(input);
Assert.AreEqual(res, output);
}
}
}
