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.
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 <= 50001 <= nums[i] <= 104Problem Overview: You are given an integer array nums. In one operation, you can increment any element by 1. The goal is to make the array strictly increasing with the minimum number of operations.
Approach 1: Iterative Adjustment (Greedy) (Time: O(n), Space: O(1))
The most direct solution is a greedy scan from left to right. For every index i, the value must be strictly greater than the previous element nums[i-1]. If nums[i] is already greater, continue. Otherwise, increment it until it becomes nums[i-1] + 1. The number of increments required is (nums[i-1] + 1 - nums[i]), which you add to the operation count. Then update the current element to the new value so the next comparison remains valid.
This works because the smallest valid value for each position is always previous + 1. Any larger increase would only add unnecessary operations. The algorithm performs a single pass through the array and modifies values greedily, making it optimal for problems involving monotonic constraints on an array. Time complexity is O(n) and space complexity is O(1).
Approach 2: Difference Array Method (Time: O(n), Space: O(n))
This method models the required increments using a difference-style adjustment. Instead of directly modifying the array, compute how far each element is from the minimum valid value needed to maintain a strictly increasing sequence. For each index i, the expected minimum value is max(nums[i], prev + 1). The difference between the expected value and the original value represents the number of increments needed.
You can store these increments in an auxiliary structure (similar to a difference or adjustment array) and accumulate them while tracking the running valid value. This approach separates calculation from mutation, which can help when the original array must remain unchanged. The algorithm still performs a single linear pass, so the time complexity remains O(n), while storing adjustments increases the space complexity to O(n). The logic still relies on a greedy decision: always raise each element to the smallest value that keeps the sequence strictly increasing.
Recommended for interviews: The Iterative Adjustment (Greedy) approach is the expected solution. Interviewers look for the key observation that each element only needs to become previous + 1 when the order breaks. Demonstrating the greedy reasoning and implementing the single-pass O(n) solution shows strong understanding of array traversal and constraint maintenance.
This approach involves iterating through the array and ensuring each element is greater than the previous one by directly modifying the array elements. We keep track of how many operations are needed to achieve this and return the total operations as the result.
We iterate over the array starting from the second element. If the current element is not greater than the previous one, we calculate the number of increments needed to make it strictly greater and increment the operation count accordingly, adjusting the current element.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), as we are modifying the array in place.
This method involves calculating differences between consecutive elements. If any difference is not positive, operations are added to make it positive, and we update the current element. This approach implicitly highlights where and how much adjustment is needed to ensure array elements strictly increase.
By calculating differences and adjusting only when the difference is non-positive, this solution minimizes operations effectively by correcting necessary parts directly.
Time Complexity: O(n), where n is array size.
Space Complexity: O(1), applying in-place corrections.
We use a variable mx to record the maximum value of the current strictly increasing array, initially mx = 0.
Traverse the array nums from left to right. For the current element v, if v \lt mx + 1, we need to increase it to mx + 1 to ensure the array is strictly increasing. Therefore, the number of operations we need to perform this time is max(0, mx + 1 - v), which is added to the answer, and then we update mx=max(mx + 1, v). Continue to traverse the next element until the entire array is traversed.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Iterative Adjustment | Time Complexity: O(n), where n is the length of the array. |
| Difference Array Method | Time Complexity: O(n), where n is array size. |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Adjustment (Greedy) | O(n) | O(1) | Best general solution; single pass and constant memory |
| Difference Array Method | O(n) | O(n) | Useful when you want to track increments separately without mutating the original array |
Leetcode 1827. Minimum Operations to Make the Array Increasing #biweekly contest • Code with Alisha • 15,240 views views
Watch 9 more video solutions →Practice Minimum Operations to Make the Array Increasing with our built-in code editor and test cases.
Practice on FleetCode