Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1827.html

1827. Minimum Operations to Make the Array Increasing

Level

Easy

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^4

Solution

To make nums strictly increasing, each element in nums must be greater than its previous element. For all 1 <= i < nums.length - 1, nums[i] must be at least nums[i - 1] + 1, so let minCurr = Math.max(nums[i], nums[i - 1] + 1), add minCurr - nums[i] to the number of operations, and let nums[i] = minCurr. Finally, return the number of operations.

  • class Solution {
    public int minOperations(int[] nums) {
        int operations = 0;
        int length = nums.length;
        for (int i = 1; i < length; i++) {
            int prev = nums[i - 1], curr = nums[i];
            int minCurr = Math.max(prev + 1, curr);
            operations += minCurr - curr;
            nums[i] = minCurr;
        }
        return operations;
    }
}

############

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

  • // OJ: https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minOperations(vector<int>& A) {
        int ans = 0;
        for (int i = 1; i < A.size(); ++i) {
            int tmp = A[i];
            A[i] = max(A[i], A[i - 1] + 1);
            ans += A[i] - tmp;
        }
        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

############

# 1827. Minimum Operations to Make the Array Increasing
# https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing/

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0

        for i in range(1, n):
            if nums[i] <= nums[i - 1]:
                d = nums[i - 1] + 1
                res += d - nums[i]
                nums[i] = d
    
        return res


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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

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

All Problems

All Solutions