Decrease elements to make array zigzag

Array Greedy

49.0% acceptance

Feb 25, 2026

459

169

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn moves_to_make_zigzag(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut res = [0i32; 2];
    for i in 0..n {
      // For pattern p, position i is a valley when i%2 == p
      let neighbors = [
        if i > 0 { nums[i-1] } else { i32::MAX },
        if i + 1 < n { nums[i+1] } else { i32::MAX },
      ];
      let min_neighbor = neighbors[0].min(neighbors[1]);
      let cost = 0i32.max(nums[i] - min_neighbor + 1);
      res[i % 2] += cost;
    }
    res[0].min(res[1])
  }
}