Minimum Increment Operations to Make Array Beautiful — LeetCode 2919 Python Solution

The problem

You are given a 0-indexed integer array nums having length n, and an integer k. You can perform the following increment operation any number of times (including zero): Choose an index i in the range [0, n - 1], and increase nums[i] by 1.

Example

Input

nums = [2,3,0,0,2], k = 4

Output

3

Explanation

We can perform the following increment operations to make nums beautiful:

Python solution

class Solution:
    def minIncrementOperations(self, nums: List[int], k: int) -> int:
        f = g = h = 0
        for x in nums:
            f, g, h = g, h, min(f, g, h) + max(k - x, 0)
        return min(f, g, h)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 2919. Minimum Increment Operations to Make Array Beautiful is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems