Problem

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.

  • For example, if nums = [1,2,3], you can choose to increment nums[1] to make nums = [1,_**3**_ ,3].

Return theminimum 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.

Examples

Example 1

1
2
3
4
5
6

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

1
2

Input: nums = [1,5,2,4,1]
Output: 14

Example 3

1
2

Input: nums = [8]
Output: 0

Constraints

  • 1 <= nums.length <= 5000
  • 1 <= nums[i] <= 10^4

Solution

Method 1 – Greedy Increment

Intuition

To make the array strictly increasing, whenever nums[i] is not greater than nums[i-1], we must increment nums[i] enough to make it one more than nums[i-1]. The minimum number of operations is the sum of all such increments.

Approach

  1. Iterate through the array from left to right.
  2. For each index i > 0, if nums[i] <= nums[i-1], increment nums[i] by (nums[i-1] - nums[i] + 1) and add this to the answer.
  3. Continue until the end of the array.
  4. Edge case: If the array is already strictly increasing, answer is 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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]) {
                ans += nums[i-1] - nums[i] + 1;
                nums[i] = nums[i-1] + 1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func minOperations(nums []int) int {
    ans := 0
    for i := 1; i < len(nums); i++ {
        if nums[i] <= nums[i-1] {
            ans += nums[i-1] - nums[i] + 1
            nums[i] = nums[i-1] + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int minOperations(int[] nums) {
        int ans = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] <= nums[i-1]) {
                ans += nums[i-1] - nums[i] + 1;
                nums[i] = nums[i-1] + 1;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minOperations(nums: IntArray): Int {
        var ans = 0
        for (i in 1 until nums.size) {
            if (nums[i] <= nums[i-1]) {
                ans += nums[i-1] - nums[i] + 1
                nums[i] = nums[i-1] + 1
            }
        }
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def minOperations(self, nums: list[int]) -> int:
        ans = 0
        for i in range(1, len(nums)):
            if nums[i] <= nums[i-1]:
                ans += nums[i-1] - nums[i] + 1
                nums[i] = nums[i-1] + 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn min_operations(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        let mut ans = 0;
        for i in 1..nums.len() {
            if nums[i] <= nums[i-1] {
                ans += nums[i-1] - nums[i] + 1;
                nums[i] = nums[i-1] + 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minOperations(nums: number[]): number {
        let ans = 0;
        for (let i = 1; i < nums.length; i++) {
            if (nums[i] <= nums[i-1]) {
                ans += nums[i-1] - nums[i] + 1;
                nums[i] = nums[i-1] + 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once, and each operation is constant time.
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.