Minimum Operations to Make the Array Increasing — Solution
Minimum Operations to Make the Array Increasing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Operations to Make the Array Increasing is an easy coding problem on arrays and greedy, asked in Amazon and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Greedy
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums. In one operation you may increment any single element by 1.
Return the minimum number of operations needed to make nums strictly increasing — that is, nums[i] < nums[i+1] for every i.
Example 1
Input: nums = [1,1,1]
Output: 3
Explanation: Raise the array to [1,2,3]: one operation on the second element and two on the third.
Example 2
Input: nums = [1,5,2,4,1]
Output: 14
Example 3
Input: nums = [8]
Output: 0
Explanation: A single element is already strictly increasing.
Constraints
1 <= nums.length <= 50001 <= nums[i] <= 10000
Hints for Minimum Operations to Make the Array Increasing
Hint 1
You can only increase values, so the first element never changes.
Hint 2
Process left to right: each element must end strictly above the one before it.
Hint 3
Raise an element to exactly
prev + 1— never higher, since extra height only costs more later.
How to solve Minimum Operations to Make the Array Increasing
Sweep left to right and raise each element to the smallest legal value. Because operations only increase values, leaving an element as low as the rules allow is never worse for the elements that follow.
Approach
- Keep
prev, the (possibly raised) value of the previous element, starting atnums[0]. - For each later element: if
nums[i] > prev, it is already fine — setprev = nums[i]. - Otherwise add
prev + 1 - nums[i]operations and setprev = prev + 1. - Return the accumulated count.
Why it works
An exchange argument: if an optimal solution raised some element above prev + 1, lowering it to prev + 1 keeps the array strictly increasing at that position and can only reduce the work required at every later position. So the greedy choice is optimal.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Comparing against the original
nums[i-1]instead of the raisedprevundercounts on runs like[1,1,1]. - Raising to
prevrather thanprev + 1yields a non-decreasing array, not a strictly increasing one. - The running total can exceed 32 bits at the upper limits in some languages — accumulate in 64 bits.
Reference solution
Python
from typing import List
def minOperations(nums: List[int]) -> int:
ops = 0
prev = nums[0]
for i in range(1, len(nums)):
if nums[i] <= prev:
ops += prev + 1 - nums[i]
prev = prev + 1
else:
prev = nums[i]
return opsJava
public static int minOperations(int[] nums) {
long ops = 0;
int prev = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] <= prev) {
ops += (long) prev + 1 - nums[i];
prev = prev + 1;
} else {
prev = nums[i];
}
}
return (int) ops;
}C++
int minOperations(vector<int>& nums) {
long long ops = 0;
int prev = nums[0];
for (int i = 1; i < (int) nums.size(); i++) {
if (nums[i] <= prev) {
ops += (long long) prev + 1 - nums[i];
prev = prev + 1;
} else {
prev = nums[i];
}
}
return (int) ops;
}JavaScript
var minOperations = function(nums) {
let ops = 0, prev = nums[0];
for (let i = 1; i < nums.length; i++) {
if (nums[i] <= prev) {
ops += prev + 1 - nums[i];
prev = prev + 1;
} else {
prev = nums[i];
}
}
return ops;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms