# Minimum Value to Get Positive Step by Step Sum
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-value-to-get-positive-step-by-step-sum)
Canonical: https://scaleengineer.com/dsa/problems/minimum-value-to-get-positive-step-by-step-sum
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Swiggy](https://scaleengineer.com/companies/swiggy)
---
## Problem
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`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We start by trying the smallest possible positive `startValue`, which is 1. We then check if it's valid by calculating the step-by-step sum. If at any point the sum drops below 1, we know this `startValue` is too small, so we increment it by 1 and try again. We repeat this process until we find the first `startValue` for which the step-by-step sum always remains 1 or greater.
**Time:** O(S * N), where N is the number of elements in `nums` and S is the final answer (the minimum start value). In the worst-case scenario (e.g., an array full of large negative numbers), S can be large, making the algorithm slow. · **Space:** O(1), as it only uses a few variables to store the `startValue`, the running total, and a flag. The space used does not depend on the size of the input array.
**Pros:** The logic is straightforward and easy to understand as it directly models the problem statement.; It requires minimal extra memory.
**Cons:** This approach can be slow if the required `startValue` is large, as it involves nested loops.; It performs redundant calculations by repeatedly summing up parts of the array.
### Explanation
The brute-force method systematically checks every possible positive integer for `startValue`, beginning with 1. For each candidate `startValue`, it simulates the entire process of accumulating sums. A running total, initialized with the candidate `startValue`, is updated by adding each element of the `nums` array in order. During this simulation, if the running total ever falls below 1, the candidate `startValue` is deemed invalid. The simulation for that candidate stops, and the algorithm proceeds to the next integer (`startValue + 1`). The first `startValue` that allows the simulation to complete without the sum ever dropping below 1 is guaranteed to be the minimum positive `startValue` required, and it is returned as the result.

```java
class Solution {
    public int minStartValue(int[] nums) {
        int startValue = 1;
        while (true) {
            int total = startValue;
            boolean isValid = true;
            for (int num : nums) {
                total += num;
                if (total < 1) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                return startValue;
            }
            startValue++;
        }
    }
}
```
### Algorithm
*   Initialize `startValue` to 1.
*   Start an infinite loop.
*   Inside the loop, create a variable `currentSum` and set it to `startValue`.
*   Create a boolean flag `isValid` and set it to `true`.
*   Iterate through the `nums` array. For each number:
    *   Add the number to `currentSum`.
    *   If `currentSum` becomes less than 1, it means the current `startValue` is not valid. Set `isValid` to `false` and break the inner loop.
*   After the inner loop, if `isValid` is still `true`, it means we have found the minimum positive `startValue`. Return the current `startValue`.
*   If `isValid` is `false`, increment `startValue` by 1 and continue the outer loop to test the next value.

## Single Pass with Prefix Sum
A more efficient method is to analyze the condition mathematically. The requirement is that `startValue` plus any prefix sum of `nums` must be at least 1. This implies that `startValue` must be large enough to prevent even the most negative step-by-step sum from dropping below 1. By finding the minimum prefix sum that occurs, we can directly calculate the minimum `startValue` needed to satisfy the condition in a single pass.
**Time:** O(N), where N is the number of elements in `nums`. This is because we only need to iterate through the array once to find the minimum prefix sum. · **Space:** O(1), as it only uses a couple of variables to store the running total and the minimum value, regardless of the input size.
**Pros:** Extremely efficient, solving the problem in a single pass through the input array.; Optimal time and space complexity.
**Cons:** The logic is less direct than the brute-force approach and requires a small mathematical insight to understand why it works.
### Explanation
This approach is based on a key insight. Let the step-by-step sum after considering `i` elements be `Sum_i = startValue + nums[0] + ... + nums[i-1]`. The condition is `Sum_i >= 1` for all `i`. This is equivalent to `startValue + prefixSum[i-1] >= 1`, where `prefixSum` is the sum of elements from `nums`. For this inequality to hold for all `i`, it must hold for the minimum possible prefix sum. Let `minPrefixSum` be the minimum value among all prefix sums. The condition simplifies to `startValue + minPrefixSum >= 1`. Solving for `startValue`, we get `startValue >= 1 - minPrefixSum`. Since we need the minimum positive `startValue`, we can find the `minPrefixSum` by iterating through the array once. We maintain a running sum and a variable to track the minimum sum seen so far. The final answer is then `1 - minPrefixSum`.

```java
class Solution {
    public int minStartValue(int[] nums) {
        int minVal = 0;
        int total = 0;
        for (int num : nums) {
            total += num;
            minVal = Math.min(minVal, total);
        }
        // The minimum startValue should be such that:
        // startValue + minVal >= 1
        // startValue >= 1 - minVal
        return 1 - minVal;
    }
}
```
### Algorithm
*   Initialize two integer variables: `total` to 0 (to keep track of the running sum) and `minVal` to 0 (to keep track of the minimum running sum encountered).
*   Iterate through each number `num` in the `nums` array.
*   In each iteration, add `num` to `total`.
*   Update `minVal` to be the minimum of its current value and the new `total` (i.e., `minVal = min(minVal, total)`).
*   After the loop finishes, `minVal` will hold the minimum prefix sum. If all prefix sums were positive, `minVal` will be 0.
*   The condition to satisfy is `startValue + minVal >= 1`.
*   To find the minimum `startValue`, we solve for it: `startValue >= 1 - minVal`.
*   The smallest integer `startValue` is therefore `1 - minVal`. Return this value.

# Solutions
### Java

```java
class Solution {
public
  int minStartValue(int[] nums) {
    int s = 0;
    int t = Integer.MAX_VALUE;
    for (int num : nums) {
      s += num;
      t = Math.min(t, s);
    }
    return Math.max(1, 1 - t);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minStartValue(vector<int> &nums) {
    int s = 0, t = INT_MAX;
    for (int num : nums) {
      s += num;
      t = min(t, s);
    }
    return max(1, 1 - t);
  }
};

```

### Python

```python
class Solution : def minStartValue ( self , nums : List [ int ]) -> int : s , t = 0 , inf for num in nums : s += num t = min ( t , s ) return max ( 1 , 1 - t )
```