Minimum Operations To Make The Array Increasing - Leetcode Solution

Problem Statement:

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 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[1], so nums becomes [1,2,1].
2. Increment nums[2], so nums becomes [1,2,2].
3. Increment nums[1], so nums becomes [1,3,2]. Example 2:

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

Input: nums = [8] Output: 0

Approach:

To make the array strictly increasing, we need to make sure that nums[i] < nums[i+1]. If the condition doesn't hold true, then we need to make at least one operation to increase the value of nums[i+1]. We can then repeat this process until the condition holds true for all pairs (nums[i], nums[i+1]).

To keep track of the number of operations, we can maintain a variable called "ans". Initially, ans will be zero. Whenever we encounter a pair (nums[i], nums[i+1]) where nums[i] >= nums[i+1], we need to make some operations.

We can calculate the number of operations as follows:

increment = nums[i] - (nums[i+1] - 1) ans += increment nums[i+1] = nums[i] + 1

Explanation:

increment is the difference between nums[i] and (nums[i+1] - 1). We subtract 1 from nums[i+1] because we want to make sure that nums[i+1] is greater than nums[i]. We add increment to the variable ans to keep track of the total number of operations. Finally, we update nums[i+1] to nums[i]+1 as we have incremented its value.

Code:

The code for the approach discussed above is given below:

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

The time complexity of this approach is O(n) where n is the length of the array nums. This is because we are iterating through the array only once. The space complexity of this approach is O(1) as we are not using any extra space for computations.

The solution got accepted on the first try with a runtime of 36ms (faster than 100% of python submissions) and 14.3MB of memory usage (less than 29% of Python3 submissions).

1