Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1144. Decrease Elements To Make Array Zigzag - Leetcode Solution

Code Implementation

class Solution:
    def movesToMakeZigzag(self, nums):
        def moves(nums, is_even):
            res = 0
            n = len(nums)
            for i in range(n):
                if (i % 2 == 0) == is_even:
                    left = nums[i - 1] if i - 1 >= 0 else float('inf')
                    right = nums[i + 1] if i + 1 < n else float('inf')
                    min_adj = min(left, right)
                    if nums[i] >= min_adj:
                        res += nums[i] - min_adj + 1
            return res
        return min(moves(nums, True), moves(nums, False))
      
class Solution {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        return min(helper(nums, 0), helper(nums, 1));
    }
    int helper(vector<int>& nums, int even) {
        int n = nums.size(), res = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == even) {
                int left = (i > 0) ? nums[i-1] : INT_MAX;
                int right = (i+1 < n) ? nums[i+1] : INT_MAX;
                int min_adj = min(left, right);
                if (nums[i] >= min_adj) {
                    res += nums[i] - min_adj + 1;
                }
            }
        }
        return res;
    }
};
      
class Solution {
    public int movesToMakeZigzag(int[] nums) {
        return Math.min(helper(nums, 0), helper(nums, 1));
    }
    private int helper(int[] nums, int even) {
        int n = nums.length, res = 0;
        for (int i = 0; i < n; ++i) {
            if (i % 2 == even) {
                int left = (i > 0) ? nums[i-1] : Integer.MAX_VALUE;
                int right = (i+1 < n) ? nums[i+1] : Integer.MAX_VALUE;
                int minAdj = Math.min(left, right);
                if (nums[i] >= minAdj) {
                    res += nums[i] - minAdj + 1;
                }
            }
        }
        return res;
    }
}
      
var movesToMakeZigzag = function(nums) {
    function moves(nums, even) {
        let res = 0, n = nums.length;
        for (let i = 0; i < n; ++i) {
            if ((i % 2 === 0) === even) {
                let left = i > 0 ? nums[i-1] : Infinity;
                let right = i+1 < n ? nums[i+1] : Infinity;
                let minAdj = Math.min(left, right);
                if (nums[i] >= minAdj) {
                    res += nums[i] - minAdj + 1;
                }
            }
        }
        return res;
    }
    return Math.min(moves(nums, true), moves(nums, false));
};

Problem Description

Given an array of integers nums, your goal is to make the array "zigzag" by decreasing the values of some elements. A "zigzag" array means that either:
  • Every even-indexed element is greater than its adjacent elements (nums[0] > nums[1] < nums[2] > nums[3] < ...), or
  • Every odd-indexed element is greater than its adjacent elements (nums[0] < nums[1] > nums[2] < nums[3] > ...).
In one move, you can decrease any element by 1 (as many times as you want). Find the minimum number of moves required to make nums a zigzag array.

Thought Process

The first idea is to check both possible zigzag patterns: one where even indices are peaks, and one where odd indices are peaks. For each pattern, we need to ensure that every "peak" is strictly greater than its neighbors, and every "valley" is strictly less.

A brute-force approach would try every possible combination of decreases, but that's inefficient. Instead, we can independently consider each index: for each position that needs to be a valley, we only need to decrease it enough so it's strictly less than both neighbors. This leads us to a greedy, local-minimum approach.

Solution Approach

To solve the problem efficiently, we follow these steps:
  • Step 1: For both possible zigzag patterns (even-indexed peaks and odd-indexed peaks), calculate the number of decreases needed.
  • Step 2: For each index that needs to be a valley, check its left and right neighbors (if they exist). If nums[i] is not strictly less than the minimum of its neighbors, decrease nums[i] just enough so that nums[i] < min(neighbors).
  • Step 3: Sum the number of decreases across the array for each pattern.
  • Step 4: The answer is the minimum of the two totals.
We use simple iteration and comparison for each element. No extra data structures are required except for counters.

Example Walkthrough

Let's use nums = [2, 7, 10, 9, 8, 9].
  • Even-indexed peaks: We want nums[0], nums[2], nums[4] to be peaks.
  • For nums[1]: it should be a valley. Neighbors are 2 and 10. Since 7 < min(2,10)=2 is false, so decrease 7 to 1 (6 moves).
  • For nums[3]: neighbors 10 and 8. 9 < min(10,8)=8 is false, so decrease 9 to 7 (2 moves).
  • For nums[5]: neighbor 8. 9 < 8 is false, so decrease 9 to 7 (2 moves).
  • Total moves for even-indexed peaks: 6 + 2 + 2 = 10.
  • Odd-indexed peaks: Now nums[1], nums[3], nums[5] are peaks.
  • For nums[0]: neighbor 7. 2 < 7 is true, so 0 moves.
  • For nums[2]: neighbors 7 and 9. 10 < min(7,9)=7 is false, decrease 10 to 6 (4 moves).
  • For nums[4]: neighbors 9 and 9. 8 < min(9,9)=9 is true, so 0 moves.
  • Total moves for odd-indexed peaks: 4 moves.
The minimum is 4 moves.

Time and Space Complexity

  • Brute-force approach: Exponential time, as it would try all possible combinations of decreases for all elements.
  • Optimized approach (this solution): O(n) time, because we scan the array twice (once for each pattern), and each scan is O(n).
  • Space complexity: O(1) extra space, as we only use counters and a few variables.

Summary

The key insight is that we can treat each index independently for both possible zigzag patterns, making local adjustments only where needed. By considering both even and odd peaks and summing the required decreases, we avoid brute-force and achieve an efficient solution. This greedy, local-minimum approach is both elegant and practical.