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