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] <= 104The key idea behind solving #1827 Minimum Operations to Make the Array Increasing is to ensure that every element in the array is strictly greater than the previous one. Since you are only allowed to increment values, a greedy strategy works well.
Traverse the array from left to right and keep track of the value that the current element must exceed. If the current value is already greater than the previous one, you can continue without changes. Otherwise, you must perform enough increment operations to make the element previous + 1. Add these increments to your total operation count and update the expected previous value.
This approach works because making the smallest possible increment at each step preserves the minimal number of operations overall. The algorithm requires only a single pass through the array and a few variables to track the previous value and total operations.
Time complexity is linear since each element is processed once, and space complexity is constant because no extra data structures are required.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy single-pass traversal | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
nums[i+1] must be at least equal to nums[i] + 1.
Think greedily. You don't have to increase nums[i+1] beyond nums[i]+1.
Iterate on i and set nums[i] = max(nums[i-1]+1, nums[i]) .
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, similar array and greedy problems are commonly asked in FAANG and other top tech company interviews. They test a candidate's ability to reason about constraints, perform efficient traversals, and apply greedy decision-making.
No special data structure is required for this problem. A simple array traversal with a few variables to track the previous value and the total number of operations is sufficient.
The optimal approach uses a greedy strategy. Traverse the array and ensure each element is strictly greater than the previous one, incrementing it when necessary. By always making the smallest possible increment, you minimize the total number of operations.
The greedy approach works because increasing an element to the smallest valid value keeps future options flexible while minimizing operations. Any larger increment would only increase the total cost without providing additional benefit.