Minimum Operations to Make the Array Increasing

Easy
498.

Minimum Operations to Make the Array Increasing

Minimum Operations to Make the Array Increasing is an easy coding problem on arrays and greedy, asked in Amazon and Microsoft interviews.

You are given an integer array nums. In one operation you may increment any single element by 1.

Return the minimum number of operations needed to make nums strictly increasing — that is, nums[i] < nums[i+1] for every i.

Example 1

Input
nums = [1,1,1]
Output
3
Explanation
Raise the array to [1,2,3]: one operation on the second element and two on the third.

Example 2

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

Example 3

Input
nums = [8]
Output
0
Explanation
A single element is already strictly increasing.

Constraints

  • 1 <= nums.length <= 5000
  • 1 <= nums[i] <= 10000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Make the Array Increasing — Solution

Minimum Operations to Make the Array Increasing solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Make the Array Increasing is an easy coding problem on arrays and greedy, asked in Amazon and Microsoft interviews.

  • Difficulty: Easy
  • Topics: Arrays, Greedy
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums. In one operation you may increment any single element by 1.

Return the minimum number of operations needed to make nums strictly increasing — that is, nums[i] < nums[i+1] for every i.

Example 1

Input: nums = [1,1,1]
Output: 3
Explanation: Raise the array to [1,2,3]: one operation on the second element and two on the third.

Example 2

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

Example 3

Input: nums = [8]
Output: 0
Explanation: A single element is already strictly increasing.

Constraints

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

Hints for Minimum Operations to Make the Array Increasing

  1. Hint 1

    You can only increase values, so the first element never changes.

  2. Hint 2

    Process left to right: each element must end strictly above the one before it.

  3. Hint 3

    Raise an element to exactly prev + 1 — never higher, since extra height only costs more later.

How to solve Minimum Operations to Make the Array Increasing

Sweep left to right and raise each element to the smallest legal value. Because operations only increase values, leaving an element as low as the rules allow is never worse for the elements that follow.

Approach

  1. Keep prev, the (possibly raised) value of the previous element, starting at nums[0].
  2. For each later element: if nums[i] > prev, it is already fine — set prev = nums[i].
  3. Otherwise add prev + 1 - nums[i] operations and set prev = prev + 1.
  4. Return the accumulated count.

Why it works

An exchange argument: if an optimal solution raised some element above prev + 1, lowering it to prev + 1 keeps the array strictly increasing at that position and can only reduce the work required at every later position. So the greedy choice is optimal.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Comparing against the original nums[i-1] instead of the raised prev undercounts on runs like [1,1,1].
  • Raising to prev rather than prev + 1 yields a non-decreasing array, not a strictly increasing one.
  • The running total can exceed 32 bits at the upper limits in some languages — accumulate in 64 bits.

Reference solution

Python

from typing import List

def minOperations(nums: List[int]) -> int:
    ops = 0
    prev = nums[0]
    for i in range(1, len(nums)):
        if nums[i] <= prev:
            ops += prev + 1 - nums[i]
            prev = prev + 1
        else:
            prev = nums[i]
    return ops

Java

public static int minOperations(int[] nums) {
    long ops = 0;
    int prev = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] <= prev) {
            ops += (long) prev + 1 - nums[i];
            prev = prev + 1;
        } else {
            prev = nums[i];
        }
    }
    return (int) ops;
}

C++

int minOperations(vector<int>& nums) {
    long long ops = 0;
    int prev = nums[0];
    for (int i = 1; i < (int) nums.size(); i++) {
        if (nums[i] <= prev) {
            ops += (long long) prev + 1 - nums[i];
            prev = prev + 1;
        } else {
            prev = nums[i];
        }
    }
    return (int) ops;
}

JavaScript

var minOperations = function(nums) {
    let ops = 0, prev = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] <= prev) {
            ops += prev + 1 - nums[i];
            prev = prev + 1;
        } else {
            prev = nums[i];
        }
    }
    return ops;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Greedy Algorithms