Decrease Elements To Make Array Zigzag: Greedy Two-Pass Strategy

Given an integer array nums, you can decrease any element by 1 as many times as you want. A zigzag array is one where every element is strictly less than both its neighbors, alternating between "peaks" and "valleys." Specifically, either nums[0] > nums[1] < nums[2] > nums[3] < ... or nums[0] < nums[1] > nums[2] < nums[3] > .... Return the minimum number of operations (decreases by 1) to make the array zigzag.

This is LeetCode 1144: Decrease Elements To Make Array Zigzag, a medium problem that seems tricky at first because you have two possible zigzag directions. The key insight is that you try both options independently and pick the cheaper one. Each option reduces to a single linear scan with greedy local adjustments.

Why this problem matters

This problem teaches a pattern that shows up frequently: when there are a small number of global configurations to choose from, try each one greedily and compare. Instead of searching a combinatorial space, you fix the high-level choice (which indices are valleys?) and then compute the optimal cost for that fixed choice.

The local adjustment logic is also reusable. At each valley position, you look at both neighbors and compute exactly how much you need to decrease to satisfy the constraint. No backtracking, no dynamic programming. Just a single pass with local decisions.

The brute force approach

The naive approach would try every possible combination of decreases. Since you can decrease each element by any amount, the search space is enormous. Even a smarter brute force that tries both zigzag directions but re-examines dependencies between elements ends up with complicated logic.

The issue is that decreasing one element can affect the constraints on its neighbors. If you are not careful about the order of operations, you end up making unnecessary adjustments.

The key insight: only decrease valley elements

Here is the critical observation: you never need to decrease a peak element. Peaks need to be larger than their neighbors. Decreasing a peak only makes the constraint harder to satisfy. You only ever decrease valley elements to make them smaller than their neighbors.

But wait. You might also need to decrease a neighbor of a valley to make the valley satisfy its constraint. Actually, no. You can always make a valley satisfy its constraint by decreasing the valley element itself. Decreasing a non-valley element could introduce new violations at its own neighbors.

The cleanest strategy is:

1. Fix which indices are valleys (even indices or odd indices).
2. For each valley index, if it is not already strictly less than both neighbors, decrease the neighbor that is in the way. Actually, re-read the problem: you can decrease any element. The optimal move is to decrease the elements at non-valley positions so each valley naturally sits below its neighbors. But there is an even simpler way to think about it.

For a given set of valley indices, look at each non-valley index i. Element nums[i] must be strictly greater than both its neighbors. If nums[i] is not already greater, you decrease nums[i] to min(neighbors) - 1. The cost is nums[i] - (min(neighbors) - 1).

Wait, let us simplify. The standard approach is: for each valley index i, you need nums[i] to be strictly less than both neighbors. If it is not, you decrease nums[i] to be min(left, right) - 1. The cost at position i is max(0, nums[i] - min(left, right) + 1).

Walking through it step by step

Let's trace through nums = [1, 2, 3].

In Strategy A, even-indexed positions (0 and 2) must be valleys. Position 0 has only one neighbor (2), and 1 < 2, so no cost. Position 2 has only one neighbor (2), and 3 >= 2, so we decrease it to 1. Cost = 2. Total = 2.

In Strategy B, odd-indexed positions (just 1) must be valleys. Position 1 has neighbors 1 and 3. We need nums[1] to be strictly less than both, so we decrease 2 to min(1, 3) - 1 = 0. Cost = 2. Total = 2.

The answer is min(2, 2) = 2.

The greedy solution

Here is the complete solution in Python:

def moves_to_make_zigzag(nums):
    n = len(nums)
    costs = [0, 0]

    for valley_parity in range(2):
        for i in range(valley_parity, n, 2):
            left = nums[i - 1] if i > 0 else float('inf')
            right = nums[i + 1] if i < n - 1 else float('inf')
            target = min(left, right) - 1
            if nums[i] > target:
                costs[valley_parity] += nums[i] - target

    return min(costs)

Here is what each piece does:

1. Two strategies. valley_parity = 0 means even-indexed elements are valleys. valley_parity = 1 means odd-indexed elements are valleys.
2. Iterate over valley positions. For each valley index i, find the minimum of its left and right neighbors. Boundary elements have only one neighbor, so treat the missing side as infinity.
3. Compute the cost. If nums[i] is already below min(left, right), the cost is 0. Otherwise, decrease it to min(left, right) - 1. The cost is the difference.
4. Return the minimum. Whichever strategy costs fewer total operations wins.

Why greedy local adjustment works

Each valley position is independent of the others. In a zigzag pattern, no two valleys are adjacent. That means decreasing one valley element never affects the constraint at another valley. Each valley's cost can be computed in isolation.

This independence is what makes the greedy approach optimal. There is no interaction between decisions, so local optima are global optima.

Complexity analysis

Each strategy examines roughly n/2 elements, so the total work is O(n). No auxiliary arrays are needed.

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy local adjustment

The pattern of computing the optimal change at each position independently:

cost = 0
for i in target_positions:
    required = compute_requirement(i, neighbors)
    if current[i] violates required:
        cost += adjustment(current[i], required)

In this problem, the adjustment is decreasing a valley to sit below its neighbors. In Candy, the adjustment is increasing candy counts to satisfy neighbor constraints. The skeleton is the same: walk through positions, compute the local fix, accumulate the cost.

2. Try-both-options pattern

The pattern of handling a binary global choice by solving both cases and taking the better result:

cost_option_a = solve_with_constraint(option_a)
cost_option_b = solve_with_constraint(option_b)
return min(cost_option_a, cost_option_b)

This appears whenever a problem has two mutually exclusive configurations. In this problem, either even indices are valleys or odd indices are. In Maximum Sum Circular Subarray, the maximum is either a normal subarray or a wraparound subarray. In House Robber, you either rob the first house or you do not. When the number of global choices is small, trying all of them is both simple and optimal.

Edge cases

Before submitting, make sure your solution handles these:

• Single element [5]: no neighbors, so the array is trivially zigzag. Return 0.
• Two elements [2, 7]: already zigzag regardless of direction. No decreases needed.
• All equal [4, 4, 4]: you must create valleys. Both strategies require decreasing the valley elements by 1 each to break the ties.
• Already zigzag [9, 4, 7, 2, 9]: already alternates. Both strategies may have cost 0 (or one may). Return 0.
• Strictly increasing [1, 2, 3, 4, 5]: one strategy will be cheaper than the other depending on which positions become valleys.
• Length 2 equal [3, 3]: one element must be decreased by 1. Return 1.

The greedy solution handles all of these without special-case logic.

From understanding to recall

You have read the greedy solution and it makes sense. Two strategies, local adjustments, take the min. But can you write it from scratch in an interview without looking at it?

The details matter: using float('inf') for missing neighbors, computing min(left, right) - 1 as the target, and remembering to iterate with range(parity, n, 2). These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the greedy two-strategy loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "make array zigzag, minimize operations" and the code flows out without hesitation.

The greedy local adjustment pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Wiggle Subsequence - Another zigzag problem where greedy peak-valley counting gives an O(n) solution
• Wiggle Sort II - Rearranging elements into a zigzag pattern using median partitioning
• Non-Decreasing Array - A similar "fix the array with minimum changes" problem using greedy local decisions

CodeBricks breaks the zigzag array LeetCode problem into its greedy local adjustment and try-both-options building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy array transformation question shows up in your interview, you do not think about it. You just write it.