Minimum Operations to Make the Array Increasing
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
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].
Input: nums = [1,5,2,4,1]
Output: 14
Explanation: You can do the following operations:
1) Increment nums[2] four times, so nums becomes [1, 5, 6, 4, 1].
2) Increment nums[3] three times, so nums becomes [1, 5, 6, 7, 1].
3) Increment nums[4] seven times, so nums becomes [1, 5, 6, 7, 8].
Constraints
- 1 <= nums.length <= 5000
- 1 <= nums[i] <= 10^4
When solving problems where we aim to maximize or minimize results, it's key to make the best possible choice at every step—this approach is known as the "Greedy Technique." In this problem, we're in a similar situation, where choosing the optimal option at each point (incrementing the current number just enough to satisfy the strictly increasing condition) can lead to the best solution. Let's dive into thinking of a greedy approach for this!
Optimal Approach
Intuition
We need to make the array strictly increasing using the fewest increments possible. To achieve this, we can think greedily—making the best possible choice at every step. If we are greedy, we’ll ensure that we only increment a number by the minimum amount required to satisfy the condition of strict increase.
Here’s the idea: whenever the condition nums[i] < nums[i+1] is violated, we don’t increase the number blindly. Instead, we increment nums[i+1] just enough so that it becomes one more than nums[i]. Or we can say that whenever nums[i] >= nums[i+1] (the condition is violated), we know that nums[i+1] needs to be incremented to at least nums[i] + 1 to restore the condition. This ensures that the condition is satisfied with the least amount of effort, and in doing so, we can reach the optimal solution.
Example
Consider the array nums = [1, 5, 2, 4, 1].
- Compare the first two numbers, 1 and 5. Here, 1 < 5, so no increments are needed.
- Next, compare 5 and 2. The condition is violated (5 >= 2), so we increment 2 to 6 (just one more than 5). Now the array becomes [1, 5, 6, 4, 1].
- Compare 6 and 4. Again, the condition is violated (6 >= 4), so we increment 4 to 7 (just one more than 6). The array becomes [1, 5, 6, 7, 1].
- Finally, compare 7 and 1. The condition is violated again (7 >= 1), so we increment 1 to 8 (just one more than 7). The array becomes [1, 5, 6, 7, 8].
Approach
Step 1: Initialize Variables
We will need a variable operations to track the total number of increments required. Initially, it will be set to 0. This variable will accumulate the increments as we process the array.
Step 2: Traverse the Array
Start from the first element of the array and compare it with the next element. For each pair of consecutive elements nums[i] and nums[i+1], check if the condition nums[i] < nums[i+1] holds:
- If the condition is satisfied, move to the next pair.
- If the condition is violated (nums[i] >= nums[i+1]), calculate the number of increments needed to make nums[i+1] one more than nums[i], that is
increment = nums[i] - nums[i + 1] + 1.
Update nums[i+1] with the new value and add the increment to operations.
Step 3: Return the Result
After processing all elements, the operations variable will hold the total number of increments required. Return this value as the result.
Dry Run
Initial State:
nums = [1, 5, 2, 4, 1]
operations = 0
Step 1: Compare nums[0] and nums[1]
nums[0] = 1, nums[1] = 5
Condition: 1 < 5 (strictly increasing)
No action needed, move to the next step.
operations = 0
Step 2: Compare nums[1] and nums[2]
nums[1] = 5, nums[2] = 2
Condition: 5 >= 2 (not strictly increasing)
Increment nums[2] by (5 - 2 + 1 = 4) to make nums[2] = 6.
Update the array: nums = [1, 5, 6, 4, 1]
Add 4 to operations: operations = 0 + 4 = 4
Step 3: Compare nums[2] and nums[3]
nums[2] = 6, nums[3] = 4
Condition: 6 >= 4 (not strictly increasing)
Increment nums[3] by (6 - 4 + 1 = 3) to make nums[3] = 7.
Update the array: nums = [1, 5, 6, 7, 1]
Add 3 to operations: operations = 4 + 3 = 7
Step 4: Compare nums[3] and nums[4]
nums[3] = 7, nums[4] = 1
Condition: 7 >= 1 (not strictly increasing)
Increment nums[4] by (7 - 1 + 1 = 7) to make nums[4] = 8.
Update the array: nums = [1, 5, 6, 7, 8]
Add 7 to operations: operations = 7 + 7 = 14
Final State:
nums = [1, 5, 6, 7, 8]
operations = 14
Code for All Languages
C++
class Solution {
public:
// Function to calculate the minimum number of operations to make the array strictly increasing
int minOperations(vector<int>& nums) {
// Initialize operations counter
int operations = 0;
// Loop through the array, comparing each element with the next one
for (int i = 0; i < nums.size() - 1; i++) {
// If the current element is not smaller than the next element, we need to increment
if (nums[i] >= nums[i + 1]) {
// Calculate the number of increments needed to make nums[i+1] one more than nums[i]
int increment = nums[i] - nums[i + 1] + 1;
// Apply the increment to nums[i+1]
nums[i + 1] += increment;
// Add the increment to the total number of operations
operations += increment;
}
}
// Return the total number of operations
return operations;
}
};Java
class Solution {
// Function to calculate the minimum number of operations to make the array strictly increasing
public int minOperations(int[] nums) {
// Initialize operations counter
int operations = 0;
// Loop through the array, comparing each element with the next one
for (int i = 0; i < nums.length - 1; i++) {
// If the current element is not smaller than the next element, we need to increment
if (nums[i] >= nums[i + 1]) {
// Calculate the number of increments needed to make nums[i+1] one more than nums[i]
int increment = nums[i] - nums[i + 1] + 1;
// Apply the increment to nums[i+1]
nums[i + 1] += increment;
// Add the increment to the total number of operations
operations += increment;
}
}
// Return the total number of operations
return operations;
}
}
Python
class Solution:
# Function to calculate the minimum number of operations to make the array strictly increasing
def minOperations(self, nums: list[int]) -> int:
# Initialize operations counter
operations = 0
# Loop through the array, comparing each element with the next one
for i in range(len(nums) - 1):
# If the current element is not smaller than the next element, we need to increment
if nums[i] >= nums[i + 1]:
# Calculate the number of increments needed to make nums[i+1] one more than nums[i]
increment = nums[i] - nums[i + 1] + 1
# Apply the increment to nums[i+1]
nums[i + 1] += increment
# Add the increment to the total number of operations
operations += increment
# Return the total number of operations
return operations
Javascript
// Function to calculate the minimum number of operations to make the array strictly increasing
var minOperations = function(nums) {
// Initialize operations counter
let operations = 0;
// Loop through the array, comparing each element with the next one
for (let i = 0; i < nums.length - 1; i++) {
// If the current element is not smaller than the next element, we need to increment
if (nums[i] >= nums[i + 1]) {
// Calculate the number of increments needed to make nums[i+1] one more than nums[i]
let increment = nums[i] - nums[i + 1] + 1;
// Apply the increment to nums[i+1]
nums[i + 1] += increment;
// Add the increment to the total number of operations
operations += increment;
}
}
// Return the total number of operations
return operations;
};Time Complexity : O(n)
Loop: O(n)
The loop iterates through the array nums, checking each pair of adjacent elements. Since the array has n elements, the loop executes n - 1 times, which is O(n).
Operations inside the Loop: O(1)
For each iteration, the code performs a constant number of operations: a comparison, a subtraction, and an addition to update the element and the operations counter. These are all O(1) operations.
Final Time Complexity: O(n)
The total time complexity is O(n), as the loop dominates the runtime by processing each element in the array once. Thus, the overall complexity is linear with respect to the size of the input array.
Space Complexity : O(1)
Auxiliary Space Complexity: O(1)
The auxiliary space refers to the extra space used by the algorithm apart from the input. In this case, we are only using a few variables:
- operations (to keep track of the total number of increments).
- i (to loop through the array).
These variables require constant space, O(1).
Total Space Complexity: O(n)
The total space includes both the input and the auxiliary space.
The input array nums takes O(n) space, where n is the number of elements in the array.
The algorithm does not use any additional space proportional to the size of the input, except for the constant variables. Therefore, the total space complexity is O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
A circular typewriter has letters 'a' to 'z', and the pointer starts at 'a'. Each second, you can move the pointer clockwise or counterclockwise by one step or type the current character. Given a string word, calculate the minimum seconds needed to type it by minimizing movement for each character.
You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score
1. Select an element m from nums.
2. Remove the selected element m from the array.
3. Add a new element with a value of m + 1 to the array.
4. Increase your score by m.