LeetCode 1827. Minimum Operations to Make the Array Increasing Solution in Java, C++, Python & More | Explanation + Code

Description

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.

<li>For example, if <code>nums = [1,2,3]</code>, you can choose to increment <code>nums[1]</code> to make <code>nums = [1,<u><b>3</b></u>,3]</code>.</li>

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:

<li><code>1 &lt;= nums.length &lt;= 5000</code></li>

<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>

Solutions

Solution 1: Single Pass

We use a variable mx to record the maximum value of the current strictly increasing array, initially mx = 0.

Traverse the array nums from left to right. For the current element v, if v \lt mx + 1, we need to increase it to mx + 1 to ensure the array is strictly increasing. Therefore, the number of operations we need to perform this time is max(0, mx + 1 - v), which is added to the answer, and then we update mx=max(mx + 1, v). Continue to traverse the next element until the entire array is traversed.

The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).

PythonJavaC++GoTypeScriptRustC#C

class Solution: def minOperations(self, nums: List[int]) -> int: ans = mx = 0 for v in nums: ans += max(0, mx + 1 - v) mx = max(mx + 1, v) return ans(code-box)

class Solution { public int minOperations(int[] nums) { int ans = 0, mx = 0; for (int v : nums) { ans += Math.max(0, mx + 1 - v); mx = Math.max(mx + 1, v); } return ans; } }(code-box)

class Solution { public: int minOperations(vector<int>& nums) { int ans = 0, mx = 0; for (int& v : nums) { ans += max(0, mx + 1 - v); mx = max(mx + 1, v); } return ans; } };(code-box)

func minOperations(nums []int) (ans int) { mx := 0 for _, v := range nums { ans += max(0, mx+1-v) mx = max(mx+1, v) } return }(code-box)

function minOperations(nums: number[]): number { let ans = 0; let max = 0; for (const v of nums) { ans += Math.max(0, max + 1 - v); max = Math.max(max + 1, v); } return ans; }(code-box)

impl Solution { pub fn min_operations(nums: Vec<i32>) -> i32 { let mut ans = 0; let mut max = 0; for &v in nums.iter() { ans += (0).max(max + 1 - v); max = v.max(max + 1); } ans } }(code-box)

public class Solution { public int MinOperations(int[] nums) { int ans = 0, mx = 0; foreach (int v in nums) { ans += Math.Max(0, mx + 1 - v); mx = Math.Max(mx + 1, v); } return ans; } }(code-box)

#define max(a, b) (((a) > (b)) ? (a) : (b)) int minOperations(int* nums, int numsSize) { int ans = 0; int mx = 0; for (int i = 0; i < numsSize; i++) { ans += max(0, mx + 1 - nums[i]); mx = max(mx + 1, nums[i]); } return ans; }(code-box)