{x}
blog image

Minimum Operations to Make the Array Increasing

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[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:

  • 1 <= nums.length <= 5000
  • 1 <= nums[i] <= 104

Solution Explanation: Minimum Operations to Make the Array Increasing

The problem asks for the minimum number of operations needed to make an array strictly increasing. A strictly increasing array means that each element is strictly greater than the previous element (nums[i] < nums[i+1]). We achieve this by incrementing elements.

Approach: Greedy Single Pass

The most efficient approach is a greedy algorithm that iterates through the array only once. The core idea is to maintain a running maximum (mx) representing the largest value encountered so far in a strictly increasing sequence.

Algorithm:

  1. Initialization: Initialize ans (the total operations count) and mx (the running maximum) to 0.
  2. Iteration: Iterate through the array nums:
    • For each element v:
      • Calculate the difference needed to make the current element greater than the running maximum: diff = max(0, mx + 1 - v). If v is already greater than mx + 1, diff will be 0.
      • Add diff to ans (this is the number of operations for the current element).
      • Update mx to max(mx + 1, v): This ensures mx stays as the largest value seen so far in the strictly increasing subsequence.
  3. Return: Return ans, the total number of operations.

Time and Space Complexity Analysis

  • Time Complexity: O(n), where n is the length of the input array. We iterate through the array once.
  • Space Complexity: O(1). We only use a few constant extra variables.

Code Examples (with explanations inline)

The following code examples demonstrate the solution in several programming languages. The core logic remains the same across all implementations.

Python:

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        ans = 0  # Initialize the total operations count
        mx = 0   # Initialize the running maximum
        for v in nums:  # Iterate through the array
            ans += max(0, mx + 1 - v) # Calculate and add operations needed for current element
            mx = max(mx + 1, v)       # Update the running maximum
        return ans

Java:

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

C++:

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

The other languages (Go, TypeScript, Rust, C#, C) follow a very similar structure, reflecting the simplicity and efficiency of the single-pass greedy approach. The core logic of calculating the difference and updating the maximum remains consistent.