Skip to content

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)\).

1
2
3
4
5
6
7
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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;
    }
};

1
2
3
4
5
6
7
8
func minOperations(nums []int) (ans int) {
    mx := 0
    for _, v := range nums {
        ans += max(0, mx+1-v)
        mx = max(mx+1, v)
    }
    return
}

1
2
3
4
5
6
7
8
9
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#define max(a, b) (((a) > (b)) ? (a) : (b))

int minOperations(int* nums, int numsSize) {
    int ans = 0;
    int mx = 0;
    for (int i = 0; i < numsSize; i++) {
        ans += max(0, mx + 1 - nums[i]);
        mx = max(mx + 1, nums[i]);
    }
    return ans;
}

Comments