# Minimum Operations to Make the Array Increasing
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-the-array-increasing
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank)
---
## Problem
You are given an integer array `nums` (**0-indexed**). In one operation, you can choose an element of the array and increment it by `1`.

* For example, if `nums = [1,2,3]`, you can choose to increment `nums[1]` to make `nums = [1,**3**,3]`.

Return _the **minimum** number of operations needed to make_ `nums` _**strictly** **increasing**._

An array `nums` is **strictly increasing** if `nums[i] < nums[i+1]` for all `0 <= i < nums.length - 1`. An array of length `1` is trivially strictly increasing.

**Example 1:**

**Input:** nums = [1,1,1]
**Output:** 3
**Explanation:** You can do the following operations:
1) Increment nums[2], so nums becomes [1,1,**2**].
2) Increment nums[1], so nums becomes [1,**2**,2].
3) Increment nums[2], so nums becomes [1,2,**3**].

**Example 2:**

**Input:** nums = [1,5,2,4,1]
**Output:** 14

**Example 3:**

**Input:** nums = [8]
**Output:** 0

**Constraints:**

* `1 <= nums.length <= 5000`
* `1 <= nums[i] <= 104`

# Approaches
## Single-Pass Greedy Approach
The problem asks for the minimum number of operations to make an array strictly increasing. An operation consists of incrementing an element by 1. A greedy approach is optimal here. We can iterate through the array from the second element and ensure that each element `nums[i]` is strictly greater than the previous element `nums[i-1]`. If it's not, we must increment `nums[i]` to the smallest possible value that satisfies the condition, which is `nums[i-1] + 1`. The number of increments required for this step is added to our total count. By making the smallest necessary change at each step, we ensure the overall number of operations is minimized.
**Time:** O(N), where N is the length of the input array `nums`. This is because we perform a single pass through the array from the second element to the end. · **Space:** O(1). We only use a few variables to store the operation count and the loop index. The modifications are done in-place on the input array, so no additional space proportional to the input size is required.
**Pros:** It's a very efficient solution with linear time complexity.; The logic is straightforward and easy to implement.; It uses constant extra space, making it very memory-efficient.
**Cons:** The described implementation modifies the input array. If the original array must be preserved, a slight modification is needed (e.g., using an extra variable to track the previous element's required value instead of updating the array in-place).
### Explanation
This approach involves a single pass through the array. We maintain a running count of the operations. Starting from the second element, we compare it with its predecessor. If `nums[i] <= nums[i-1]`, we've found a violation of the strictly increasing property. To correct this with the minimum number of operations, we must increase `nums[i]` until it is exactly one greater than `nums[i-1]`. The number of operations needed for this specific element is the difference between the target value (`nums[i-1] + 1`) and its current value (`nums[i]`). We add this difference to our total operation count and, importantly, update `nums[i]` to this new value (`nums[i-1] + 1`) so that the subsequent element `nums[i+1]` is compared against the corrected value. This greedy choice is optimal because making `nums[i]` any larger would only increase the total operations and impose a stricter (higher) minimum for all subsequent elements.

```java
class Solution {
    public int minOperations(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }

        int operations = 0;

        for (int i = 1; i < nums.length; i++) {
            // If the current element is not strictly greater than the previous one
            if (nums[i] <= nums[i-1]) {
                // Calculate the number of operations needed for the current element
                int requiredValue = nums[i-1] + 1;
                operations += requiredValue - nums[i];
                
                // Update the current element to its new minimum value
                nums[i] = requiredValue;
            }
        }

        return operations;
    }
}
```
### Algorithm
- Initialize a variable `operations` to 0 to store the total number of increments.
- Iterate through the array `nums` from the second element (index `i = 1`) to the end.
- At each index `i`, check if the current element `nums[i]` is less than or equal to the previous element `nums[i-1]`.
- If `nums[i] <= nums[i-1]`, the strictly increasing property is violated.
- To fix this, `nums[i]` must be at least `nums[i-1] + 1`. The minimum number of operations to achieve this is `(nums[i-1] + 1) - nums[i]`.
- Add this value to the `operations` count.
- Update `nums[i]` to `nums[i-1] + 1`. This is crucial because the next element `nums[i+1]` will be compared against this new, corrected value of `nums[i]`.
- If `nums[i] > nums[i-1]`, the condition is already satisfied, so we do nothing and move to the next element.
- After the loop completes, `operations` will hold the minimum total operations required.

# Solutions
### CSharp

```csharp
public class Solution { public int MinOperations ( int [] nums ) { int ans = 0 , mx = 0 ; foreach ( int v in nums ) { ans += Math . Max ( 0 , mx + 1 - v ); mx = Math . Max ( mx + 1 , v ); } return ans ; } }
```

### Java

```java
class Solution { public int minOperations ( int [] nums ) { int ans = 0 , mx = 0 ; for ( int v : nums ) { ans += Math . max ( 0 , mx + 1 - v ); mx = Math . max ( mx + 1 , v ); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int minOperations ( vector < int >& nums ) { int ans = 0 , mx = 0 ; for ( int & v : nums ) { ans += max ( 0 , mx + 1 - v ); mx = max ( mx + 1 , v ); } return ans ; } };
```

### Python

```python
class Solution : def minOperations ( self , nums : List [ int ]) -> int : ans = mx = 0 for v in nums : ans += max ( 0 , mx + 1 - v ) mx = max ( mx + 1 , v ) return ans
```