Problem Statement in English

You’re given an array of integers nums. In one operation, you can choose an index i such that 0 <= i < nums.length - 1 and increment nums[i] by 1.

Return the minimum number of operations needed to make nums increasing.

Approach

We can solve this problem using a greedy approach.

We will iterate through the array from the end to the beginning and check if the current element is greater than the next element.

If it is, we will increment the subsequent elements by an amount such that they are greater than the current element. That amount will be nums[i] - nums[i + 1].

We will also keep track of the number of operations needed to achieve this.

And we’re done!

Solution in Python


class Solution:
    def minOperations(self, nums: list[int]) -> int:
        res = 0
        for i in range(len(nums) - 2, -1, -1):
            if nums[i] > nums[i + 1]:
                res += nums[i] - nums[i + 1]
        return res

Complexity

  • Time: $O(n)$
    Since we traverse the array once.

  • Space: $O(1)$
    Since we are using only a constant amount of space.

Mistakes I Made

I had to look this one up :(

And we are done.