Problem statement

https://leetcode.com/problems/decrease-elements-to-make-array-zigzag/

Solution

We can have two options: do not touch odd indexes and decrease only even, or the opposite.

Complexity

It is O(n) for time and O(1) for space.

Code

class Solution:
    def movesToMakeZigzag(self, A):
        n = len(A)
        def check(s):
            ans = 0
            for i in range(s, n, 2):
                neib = float("inf")
                if i > 0: neib = min(neib, A[i - 1])
                if i + 1 < n: neib = min(neib, A[i + 1])
                ans += max(0, A[i] - neib + 1)
            return ans
        
        return min(check(0), check(1))