Watch 10 video solutions for Minimum Operations to Make the Array Increasing, a easy level problem involving Array, Greedy. This walkthrough by Code with Alisha has 15,240 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |