EasyEditorial · 5 minGenerated by the editor · Oct 12
Open — the attempt gate is not wired up yet
This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.
Intuitionwhy the smallest valid adjustment is always safe
The condition for position i depends only on the value immediately before it: nums[i] must be greater than nums[i - 1]. If nums[i] is already large enough, changing it would only add unnecessary operations. If it is too small, the cheapest valid replacement is exactly nums[i - 1] + 1, because every larger replacement uses at least as many increments.
Process the array from left to right and treat each adjusted value as the value that future positions must beat. This matters because nums[i - 1] may already have been increased earlier. Once the prefix is strictly increasing, changing an earlier element would only make the requirement for later elements harder, so the greedy choice never needs to be revisited.
Approach
1Set the operation count to zero, because every increment made during the scan contributes directly to the answer and no operation needs to be simulated one by one.
2Scan indices 1 through n - 1 from left to right, because position i can be fixed after position i - 1 is already final, while scanning in the other direction would not know the correct lower bound.
3If nums[i] is greater than nums[i - 1], leave it unchanged, because it already satisfies the strict inequality and any increment would be wasted.
4If nums[i] is less than or equal to nums[i - 1], compute need = nums[i - 1] + 1, because strict increase requires at least this value and equality is not enough.
5Add need - nums[i] to the answer and assign nums[i] = need, because that difference is exactly the number of increments required to reach the smallest valid value.
6Return the accumulated count after the scan, because every adjacent pair is then strictly increasing and each position was changed by the minimum amount compatible with the fixed prefix.
Complexityone pass and constant working memory
MEASURE
BOUND
WHY
Time
O(n)
The loop examines each index from 1 through n - 1 once, and each iteration performs only constant-time comparisons, arithmetic, and assignment. No index is revisited, so the total work is linear.
Space
O(1) extra
The algorithm updates nums in place and stores only the answer and a few scalar values; the input array is not counted as extra storage. The bound stays O(1) for every input shape, including already increasing, flat, and decreasing arrays.
CPPGreedily raise each value to the smallest number greater than the adjusted value before it.
#include <vector>
using namespace std;
class Solution {
public:
int minOperations(vector<int>& nums) {
int ans = 0;
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] <= nums[i - 1]) {
int need = nums[i - 1] + 1;
ans += need - nums[i];
nums[i] = need;
}
}
return ans;
}
};
The assignment nums[i] = need is as important as the addition to ans. The next iteration must compare against the value after its increments, not the original value stored in the array. Mutating nums in place records the final increasing prefix and makes the next greedy decision use the correct bound.
Common mistakestwo lines that change the greedy invariant