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. 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.

Examples

Example 1

1
2
3

Input: nums = [1,2,3]
Output: 2
Explanation: We can decrease 2 to 0 or 3 to 1.

Example 2

1
2

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

Constraints

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

Solution

Method 1 – Greedy Simulation for Both Zigzag Patterns

Intuition

To make the array zigzag, we can either make even indices valleys (smaller than neighbors) or odd indices valleys. For each pattern, we count the moves needed to decrease elements so that every valley is strictly less than its neighbors. The answer is the minimum of the two patterns.

Approach

  1. For both patterns (even-indexed valleys and odd-indexed valleys):
    • For each index i that should be a valley:
      • Find the minimum value of its neighbors (if they exist).
      • If nums[i] >= min(neighbor), decrease nums[i] to min(neighbor) - 1 and count the moves.
  2. Return the minimum moves from both patterns.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        int n = nums.size();
        int ans[2] = {0, 0};
        for (int parity = 0; parity < 2; ++parity) {
            for (int i = parity; i < n; i += 2) {
                int l = (i > 0) ? nums[i-1] : INT_MAX;
                int r = (i+1 < n) ? nums[i+1] : INT_MAX;
                int mn = min(l, r);
                if (nums[i] >= mn) ans[parity] += nums[i] - mn + 1;
            }
        }
        return min(ans[0], ans[1]);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func movesToMakeZigzag(nums []int) int {
    n := len(nums)
    ans := [2]int{0, 0}
    for parity := 0; parity < 2; parity++ {
        for i := parity; i < n; i += 2 {
            l, r := 1<<31-1, 1<<31-1
            if i > 0 {
                l = nums[i-1]
            }
            if i+1 < n {
                r = nums[i+1]
            }
            mn := l
            if r < mn {
                mn = r
            }
            if nums[i] >= mn {
                ans[parity] += nums[i] - mn + 1
            }
        }
    }
    if ans[0] < ans[1] {
        return ans[0]
    }
    return ans[1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        int n = nums.length;
        int[] ans = new int[2];
        for (int parity = 0; parity < 2; parity++) {
            for (int i = parity; i < n; i += 2) {
                int l = i > 0 ? nums[i-1] : Integer.MAX_VALUE;
                int r = i+1 < n ? nums[i+1] : Integer.MAX_VALUE;
                int mn = Math.min(l, r);
                if (nums[i] >= mn) ans[parity] += nums[i] - mn + 1;
            }
        }
        return Math.min(ans[0], ans[1]);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun movesToMakeZigzag(nums: IntArray): Int {
        val n = nums.size
        val ans = IntArray(2)
        for (parity in 0..1) {
            for (i in parity until n step 2) {
                val l = if (i > 0) nums[i-1] else Int.MAX_VALUE
                val r = if (i+1 < n) nums[i+1] else Int.MAX_VALUE
                val mn = minOf(l, r)
                if (nums[i] >= mn) ans[parity] += nums[i] - mn + 1
            }
        }
        return minOf(ans[0], ans[1])
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def movesToMakeZigzag(self, nums: list[int]) -> int:
        n: int = len(nums)
        ans: list[int] = [0, 0]
        for parity in (0, 1):
            for i in range(parity, n, 2):
                l = nums[i-1] if i > 0 else float('inf')
                r = nums[i+1] if i+1 < n else float('inf')
                mn = min(l, r)
                if nums[i] >= mn:
                    ans[parity] += nums[i] - mn + 1
        return min(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn moves_to_make_zigzag(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut ans = [0, 0];
        for parity in 0..2 {
            for i in (parity..n).step_by(2) {
                let l = if i > 0 { nums[i-1] } else { i32::MAX };
                let r = if i+1 < n { nums[i+1] } else { i32::MAX };
                let mn = l.min(r);
                if nums[i] >= mn {
                    ans[parity] += nums[i] - mn + 1;
                }
            }
        }
        ans[0].min(ans[1])
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    movesToMakeZigzag(nums: number[]): number {
        const n = nums.length;
        const ans = [0, 0];
        for (let parity = 0; parity < 2; parity++) {
            for (let i = parity; i < n; i += 2) {
                const l = i > 0 ? nums[i-1] : Infinity;
                const r = i+1 < n ? nums[i+1] : Infinity;
                const mn = Math.min(l, r);
                if (nums[i] >= mn) ans[parity] += nums[i] - mn + 1;
            }
        }
        return Math.min(ans[0], ans[1]);
    }
}

Complexity

  • ⏰ Time complexity: O(n), since we check each element at most twice.
  • 🧺 Space complexity: O(1), only constant extra space is used.