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:
- Increment nums[2], so nums becomes [1,1,2].
- Increment nums[1], so nums becomes [1,2,2].
- 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 andlast
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.