Decrease Elements To Make Array Zigzag — LeetCode 1144 Python Solution

The problem

Given an array nums of integers, a move consists of choosing any element and decreasing it by 1. An array A is a zigzag array if either: Every even-indexed element is greater than adjacent elements, ie.

Example

Input

nums = [1,2,3]

Output

2

Explanation

We can decrease 2 to 0 or 3 to 1.

Python solution

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        ans = [0, 0]
        n = len(nums)
        for i in range(2):
            for j in range(i, n, 2):
                d = 0
                if j:
                    d = max(d, nums[j] - nums[j - 1] + 1)
                if j < n - 1:
                    d = max(d, nums[j] - nums[j + 1] + 1)
                ans[i] += d
        return min(ans)

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 1144. Decrease Elements To Make Array Zigzag is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

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

Related problems