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. A[0] > A[1] < A[2] > A[3] < A[4] > ...
OR, every odd-indexed element is greater than adjacent elements, ie. A[0] < A[1] > A[2] < A[3] > A[4] < ...

Return the minimum number of moves to transform the given array nums into a zigzag array.
 
Example 1:
Input: nums = [1,2,3]
Output: 2
Explanation: We can decrease 2 to 0 or 3 to 1.

Example 2:
Input: nums = [9,6,1,6,2]
Output: 4

 
Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 1000

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Greedy algorithms

Starter code: class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        

Solutions:
class Solution:

	def movesToMakeZigzag(self, nums):
		n = len(nums)
		res0 = 0
		for i in range(0, n, 2):
			nei = min((nums[j] for j in [i - 1, i + 1] if 0 <= j <= n - 1))
			if nums[i] >= nei:
				res0 += nums[i] - nei + 1
		res1 = 0
		for i in range(1, n, 2):
			nei = min((nums[j] for j in [i - 1, i + 1] if 0 <= j <= n - 1))
			if nums[i] >= nei:
				res1 += nums[i] - nei + 1
		return min(res0, res1)


class Solution:

	def movesToMakeZigzag(self, nums: List[int]) -> int:
		even = odd = 0
		n = len(nums)
		for i in range(n):
			prev = nums[i - 1] if i - 1 >= 0 else float('inf')
			next = nums[i + 1] if i + 1 < n else float('inf')
			change = max(0, nums[i] - min(prev, next) + 1)
			if i % 2 == 0:
				even += change
			else:
				odd += change
		return min(even, odd)


class Solution:

	def movesToMakeZigzag(self, nums: List[int]) -> int:
		return self.sb(nums)

	def sb(self, nums):
		nums = [float('inf')] + nums + [float('inf')]
		res = [0, 0]
		for i in range(1, len(nums) - 1):
			res[i % 2] += max(0, nums[i] - min(nums[i - 1], nums[i + 1]) + 1)
		return min(res)


class Solution:

	def movesToMakeZigzag(self, nums: List[int]) -> int:
		if len(nums) <= 2:
			return 0
		n = len(nums)
		if n % 2 == 0:
			step1 = max(0, nums[-1] - nums[-2] + 1)
			for i in range(1, n - 1, 2):
				step1 += max(0, nums[i] - min(nums[i - 1], nums[i + 1]) + 1)
			step2 = max(0, nums[0] - nums[1] + 1)
			for i in range(2, n, 2):
				step2 += max(0, nums[i] - min(nums[i - 1], nums[i + 1]) + 1)
		else:
			step1 = max(0, nums[-1] - nums[-2] + 1) + max(0, nums[0] - nums[1] + 1)
			for i in range(2, n - 1, 2):
				step1 += max(0, nums[i] - min(nums[i - 1], nums[i + 1]) + 1)
			step2 = 0
			for i in range(1, n, 2):
				step2 += max(0, nums[i] - min(nums[i - 1], nums[i + 1]) + 1)
		return min(step1, step2)


class Solution:

	def movesToMakeZigzag(self, A: List[int]) -> int:
		res1 = 0
		n = len(A)
		B = A.copy()
		for i in range(1, n, 2):
			if A[i - 1] <= A[i]:
				t = A[i] - A[i - 1] + 1
				res1 += t
				A[i] = A[i - 1] - 1
			if i + 1 < n and A[i + 1] <= A[i]:
				t = A[i] - A[i + 1] + 1
				res1 += t
				A[i] = A[i + 1] - 1
		res2 = 0
		for i in range(0, n, 2):
			if i - 1 >= 0 and B[i] >= B[i - 1]:
				t = B[i] - B[i - 1] + 1
				res2 += t
				B[i] = B[i - 1] - 1
			if i + 1 < n and B[i + 1] <= B[i]:
				t = B[i] - B[i + 1] + 1
				res2 += t
				B[i] = B[i + 1] - 1
		return min(res1, res2)