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] <= 10⁴

Solutions

Solution 1: Single Pass

Thinking

We may only increment elements, and the array must become strictly increasing at minimum cost. Searching final values at each index is unnecessary.

From left to right the prefix maximum already fixes the next lower bound. If \(v\) is below \(mx+1\) we pay the difference and raise it; then \(mx\) becomes the new prefix maximum. Extra increments would only raise later bounds, so one greedy pass is optimal.

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

Python3JavaC++GoTypeScriptRustC#C

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

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

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

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

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

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

1827. Minimum Operations to Make the Array Increasing

Description

Solutions

Solution 1: Single Pass

Comments