Make Array Non-decreasing or Non-increasing — LeetCode 2263 Python Solution

The problem

You are given a 0-indexed integer array nums. In one operation, you can: Choose an index i in the range 0 <= i < nums.length Set nums[i] to nums[i] + 1 or nums[i] - 1 Return the minimum number of operations to make nums non-decreasing or non-increasing.

Example

Input

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

Output

4

Explanation

One possible way to turn nums into non-increasing order is to:

Python solution

class Solution:
    def convertArray(self, nums: List[int]) -> int:
        def solve(nums):
            n = len(nums)
            f = [[0] * 1001 for _ in range(n + 1)]
            for i, x in enumerate(nums, 1):
                mi = inf
                for j in range(1001):
                    if mi > f[i - 1][j]:
                        mi = f[i - 1][j]
                    f[i][j] = mi + abs(x - j)
            return min(f[n])

        return min(solve(nums), solve(nums[::-1]))

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2263. Make Array Non-decreasing or Non-increasing is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems