Home

Minimum Operations

A macbook side by cup of coffee Photo by Rachel Moenning

This post is part of the Algorithms Problem Solving series.

Problem description

This is the Minimum Operations problem. The description looks like this:

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.

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.

Examples

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

Solution

First solution counting and update the array in place.

def min_operations(nums):
    previous_num = nums[0]
    operations = 0

    for index, num in enumerate(nums[1:]):
        if num <= previous_num:
            new_num = previous_num - num + 1
            operations += new_num
            nums[index + 1] += new_num

        previous_num = nums[index + 1]

    return operations

Second and more optimized solution without the need to update the array.

def min_operations(nums):
    prev, ops = 0, 0

    for num in nums:
        if num <= prev:
            prev += 1
            ops += prev - num
        else:
            prev = num

    return ops

Resources

Patreon Become a Patron Coffee icon Buy me a coffee