Sponsored
Sponsored
The idea is to simulate the step by step summation of the start value with the elements of the array. We maintain a running sum and adjust the start value such that this sum never drops below 1. At each step, if the running sum is less than 1, we calculate and update the new minimum start value needed to keep the running sum at least 1.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), as we are using a constant amount of space.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int minStartValue(vector<int>& nums) {
6 int min_sum = 0, current_sum = 0;
7 for (int num : nums) {
8 current_sum += num;
9 min_sum = min(min_sum, current_sum);
10 }
11 return 1 - min_sum;
12}
13
14int main() {
15 vector<int> nums = {-3, 2, -3, 4, 2};
16 cout << minStartValue(nums) << endl; // Output: 5
17}In this C++ solution, we use std::min to consistently track the minimum cumulative sum. The final result is calculated as 1 minus the minimum sum found, ensuring that the running sum remains positive throughout.
This approach is similar to the first but conceptualized through using prefix sums and adjusting the needed start value based on the lowest prefix sum reached. We cumulatively add each number and check if the prefix sum dips below a certain threshold, indicating the minimal adjustment needed for the start value.
Time Complexity: O(n).
Space Complexity: O(1).
public class Solution {
public int MinStartValue(int[] nums) {
int minPrefixSum = 0, prefixSum = 0;
foreach (int num in nums) {
prefixSum += num;
minPrefixSum = Math.Min(minPrefixSum, prefixSum);
}
return 1 - minPrefixSum;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {-3, 2, -3, 4, 2};
Console.WriteLine(sol.MinStartValue(nums)); // Output: 5
}
}By accumulating the prefix as the loop iterates and determining where this prefix is minimal, this solution adapts the starting value to keep all steps positive throughout.