Leetcode 1827. Minimum Operations to Make the Array Increasing Solution

Problem 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

Approach

To solve this problem, we can simply iterate through the array and increment the current value if it's less than or equal to the previous value. We will do that by the difference between the previous and current values plus one. We keep track of the last value and the total number of operations done. This approach has a time complexity of O(n) since we need to iterate through the entire array.

Let's walk through a small example to better understand the approach:

Input: nums = [1, 5, 2, 4, 1] Output: 14

• Initialize ans to 0 and last to 0.
• Iterate through the array:
  • For the first number (1), we do not need any operations as this is the first element.
  • For the second number (5), we do not need any operations as it is already greater than the previous element (1).
  • For the third number (2), we need to do 5 - 2 + 1 = 4 operations to make it 6.
  • For the fourth number (4), we need to do 6 - 4 + 1 = 3 operations to make it 7.
  • For the fifth number (1), we need to do 7 - 1 + 1 = 7 operations to make it 8.
• The sum of operations done is 14, so the output is 14.

Solution

C++

1class Solution {
2 public:
3  int minOperations(vector<int>& nums) {
4    int ans = 0;
5    int last = 0;
6
7    // Iterate through the array
8    for (const int num : nums) {
9      // Increment the current value if it's less than or equal to the previous value
10      ans += max(0, last - num + 1);
11      // Keep track of the last value and the total number of operations done
12      last = max(num, last + 1);
13    }
14
15    return ans;
16  }
17};

Java

1class Solution {
2    public int minOperations(int[] nums) {
3        int ans = 0;
4        int last = 0;
5
6        // Iterate through the array
7        for (int num : nums) {
8            // Increment the current value if it's less than or equal to the previous value
9            ans += Math.max(0, last - num + 1);
10            // Keep track of the last value and the total number of operations done
11            last = Math.max(num, last + 1);
12        }
13
14        return ans;
15    }
16}

JavaScript

1class Solution {
2  minOperations(nums) {
3    let ans = 0;
4    let last = 0;
5
6    // Iterate through the array
7    for (const num of nums) {
8      // Increment the current value if it's less than or equal to the previous value
9      ans += Math.max(0, last - num + 1);
10      // Keep track of the last value and the total number of operations done
11      last = Math.max(num, last + 1);
12    }
13
14    return ans;
15  }
16}

Python

1class Solution:
2    def minOperations(self, nums: List[int]) -> int:
3        ans = 0
4        last = 0
5
6        # Iterate through the array
7        for num in nums:
8            # Increment the current value if it's less than or equal to the previous value
9            ans += max(0, last - num + 1)
10            # Keep track of the last value and the total number of operations done
11            last = max(num, last + 1)
12
13        return ans

C#

1public class Solution {
2    public int MinOperations(int[] nums) {
3        int ans = 0;
4        int last = 0;
5
6        // Iterate through the array
7        foreach (int num in nums) {
8            // Increment the current value if it's less than or equal to the previous value
9            ans += Math.Max(0, last - num + 1);
10            // Keep track of the last value and the total number of operations done
11            last = Math.Max(num, last + 1);
12        }
13
14        return ans;
15    }
16}
17```## Conclusion
18
19In this article, we have explained the problem of the minimum number of operations needed to make an array strictly increasing. The provided solution iterates through the array, increment the current value if it's less than or equal to the previous value, and keep track of the last value and the total number of operations done for all elements in the array.
20
21We have implemented the solution in Java, JavaScript, Python, C++, and C#. The time complexity of the presented solution is O(n) since we need to iterate through the entire array.