Decrease Elements To Make Array Zigzag

medium greedy array zigzag

Problem

Given an array nums, in one move you may decrease any element by 1. An array is zigzag if either every even-indexed element is greater than its neighbors, or every odd-indexed element is greater than its neighbors. Return the minimum number of moves to make nums zigzag.

Inputnums = [9, 6, 1, 6, 2]

Output4

Making odd indices the peaks: lower nums[0] from 9 to 5 (−4), nums[2] from 1 needs no change, nums[4] from 2 needs no change. Total 4 moves, which beats the even-peak pattern.

nums (comma-separated)

def moves_to_make_zigzag(nums):
    INF = float("inf")
    best = [0, 0]
    for parity in (0, 1):
        for i in range(len(nums)):
            if i % 2 != parity:
                continue
            left = nums[i - 1] if i - 1 >= 0 else INF
            right = nums[i + 1] if i + 1 < len(nums) else INF
            need = nums[i] - min(left, right) + 1
            if need > 0:
                best[parity] += need
    return min(best[0], best[1])

function movesToMakeZigzag(nums) {
  const INF = Infinity;
  const best = [0, 0];
  for (let parity = 0; parity < 2; parity++) {
    for (let i = 0; i < nums.length; i++) {
      if (i % 2 !== parity) continue;
      const left = i - 1 >= 0 ? nums[i - 1] : INF;
      const right = i + 1 < nums.length ? nums[i + 1] : INF;
      const need = nums[i] - Math.min(left, right) + 1;
      if (need > 0) best[parity] += need;
    }
  }
  return Math.min(best[0], best[1]);
}

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        int[] best = new int[2];
        for (int parity = 0; parity < 2; parity++) {
            for (int i = 0; i < nums.length; i++) {
                if (i % 2 != parity) continue;
                int left = i - 1 >= 0 ? nums[i - 1] : Integer.MAX_VALUE;
                int right = i + 1 < nums.length ? nums[i + 1] : Integer.MAX_VALUE;
                int need = nums[i] - Math.min(left, right) + 1;
                if (need > 0) best[parity] += need;
            }
        }
        return Math.min(best[0], best[1]);
    }
}

int movesToMakeZigzag(vector<int>& nums) {
    long best[2] = {0, 0};
    const int INF = INT_MAX;
    for (int parity = 0; parity < 2; parity++) {
        for (int i = 0; i < (int)nums.size(); i++) {
            if (i % 2 != parity) continue;
            int left = i - 1 >= 0 ? nums[i - 1] : INF;
            int right = i + 1 < (int)nums.size() ? nums[i + 1] : INF;
            long need = (long)nums[i] - min(left, right) + 1;
            if (need > 0) best[parity] += need;
        }
    }
    return (int)min(best[0], best[1]);
}

Explanation

A zigzag array has one set of positions that are all peaks (bigger than both neighbors). Since we can only decrease numbers, we never touch the peaks — we shrink their neighbors instead. There are just two layouts to try: peaks on even indices, or peaks on odd indices.

The key insight is that the two choices are independent. To make index i a valley (a non-peak), we only ever lower nums[i] itself, and how much we lower it depends solely on its neighbors, not on what we did elsewhere. So we can compute each layout's cost separately and take the smaller.

For a given parity (which indices should be valleys), we visit those indices and compute need = nums[i] - min(left, right) + 1. That is how far nums[i] must drop to sit strictly below its smaller neighbor. If need is positive we add it to that layout's cost; edges use INF for a missing neighbor so they never constrain.

After totaling both layouts in best[0] and best[1], the answer is min(best[0], best[1]).

Example: nums=[9,6,1,6,2]. Making the odd indices the valleys, the 6 at index 1 must drop below 1 (cost 6) — expensive; the other layout works out cheaper, and the minimum over both comes to 4.

Time: O(n) Space: O(1)