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

Difficulty: interview

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:
        # do either first case or second case
        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)
    
    '''
    걍 even 을 작게만들거나주변보다 혹은 odd를 주변보다 작게만들거나 ㅇㅇ
    '''
    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)) # 주변이 다 나보다 크면 움직이지않아도됌 :) 혹은 나보다 작은애있으면 큰만큼 + 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
        # print(A)
        # print(B)
        # print(res1,res2)
        return min(res1,res2)

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        res = [0, 0]
        
        for i in range(len(nums)):
            res[i%2] += max(nums[i] + 1 - min(nums[i-1] if i else float('inf'), nums[i+1] if i < len(nums) - 1 else float('inf')), 0)
        
        return min(res)