Difficulty: Easy | Acceptance: 82.00% | Paid: No Topics: Array, Greedy
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.
Return the minimum number of operations to make nums strictly increasing.
An array nums is strictly increasing if nums[0] < nums[1] < nums[2] < … < nums[nums.length - 1].
- Examples
- Constraints
- Greedy (Single Pass)
- Greedy (Without Modifying Array)
- Brute Force (Simulation)
Examples
Example 1:
Input: nums = [1,1,1]
Output: 3
Explanation: You can do the following three operations to make the array strictly increasing:
1. Increment nums[2] by 1. nums becomes [1,1,2].
2. Increment nums[1] by 1. nums becomes [1,2,2].
3. Increment nums[2] by 1. 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 <= 5000
1 <= nums[i] <= 10⁴
Greedy (Single Pass)
Intuition For each element, if it’s not greater than the previous element, we must increment it to exactly one more than the previous value to minimize operations.
Steps
- Initialize operations counter to 0
- Iterate through the array starting from index 1
- If current element is less than or equal to previous, calculate needed increments and update both operations and the current element
- Return total operations
from typing import List
class Solution:
def minOperations(self, nums: List[int]) -> int:
operations = 0
for i in range(1, len(nums)):
if nums[i] <= nums[i-1]:
needed = nums[i-1] + 1 - nums[i]
operations += needed
nums[i] = nums[i-1] + 1
return operations
Complexity
- Time: O(n)
- Space: O(1)
- Notes: Modifies the input array in-place
Greedy (Without Modifying Array)
Intuition Same greedy logic but track the previous value in a separate variable instead of modifying the original array.
Steps
- Initialize operations counter and prev variable with first element
- Iterate through remaining elements
- If current element is not greater than prev, calculate needed increments and update prev to prev + 1
- Otherwise, update prev to current element
- Return total operations
from typing import List
class Solution:
def minOperations(self, nums: List[int]) -> int:
if not nums:
return 0
operations = 0
prev = nums[0]
for i in range(1, len(nums)):
if nums[i] <= prev:
needed = prev + 1 - nums[i]
operations += needed
prev = prev + 1
else:
prev = nums[i]
return operations
Complexity
- Time: O(n)
- Space: O(1)
- Notes: Preserves the original array
Brute Force (Simulation)
Intuition Simulate each operation by finding the first violation and incrementing that element until the array is strictly increasing.
Steps
- Initialize operations counter to 0
- While array is not strictly increasing:
- Find the first index where nums[i] <= nums[i-1]
- Increment nums[i] by 1
- Increment operations counter
- Return total operations
from typing import List
class Solution:
def minOperations(self, nums: List[int]) -> int:
operations = 0
n = len(nums)
while True:
is_strictly_increasing = True
for i in range(1, n):
if nums[i] <= nums[i-1]:
is_strictly_increasing = False
nums[i] += 1
operations += 1
break
if is_strictly_increasing:
break
return operations
Complexity
- Time: O(n × max_operations) - can be very slow for large inputs
- Space: O(1)
- Notes: Not recommended for production use, only for understanding the problem