# 1827. Minimum Operations to Make the Array Increasing

## Description

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

## Solutions

Solution 1: Single Pass

We use a variable $mx$ to record the maximum value of the current strictly increasing array, initially $mx = 0$.

Traverse the array nums from left to right. For the current element $v$, if $v \lt mx + 1$, we need to increase it to $mx + 1$ to ensure the array is strictly increasing. Therefore, the number of operations we need to perform this time is $max(0, mx + 1 - v)$, which is added to the answer, and then we update $mx=max(mx + 1, v)$. Continue to traverse the next element until the entire array is traversed.

The time complexity is $O(n)$, where $n$ is the length of the array nums. The space complexity is $O(1)$.

• 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;
}
}

• 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;
}
};

• 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


• func minOperations(nums []int) (ans int) {
mx := 0
for _, v := range nums {
ans += max(0, mx+1-v)
mx = max(mx+1, v)
}
return
}

• function minOperations(nums: number[]): number {
let ans = 0;
let max = 0;
for (const v of nums) {
ans += Math.max(0, max + 1 - v);
max = Math.max(max + 1, v);
}
return ans;
}


• 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;
}
}


• impl Solution {
pub fn min_operations(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mut max = 0;
for &v in nums.iter() {
ans += (0).max(max + 1 - v);
max = v.max(max + 1);
}
ans
}
}