#1144

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Decrease Elements To Make Array Zigzag

Transform any integer array into a zigzag pattern with minimal decrements using a targeted greedy approach and invariant checks.

array greedy

Problem Statement

You are given an integer array nums. A move consists of selecting any element and decreasing its value by 1. The goal is to create a zigzag array, where either the even-indexed elements are strictly greater than their neighbors or the odd-indexed elements are strictly greater than their neighbors.

Return the minimum number of moves required to transform the given nums array into a zigzag pattern. The solution must consider both index patterns separately and apply decreases strategically to achieve the invariant efficiently.

Examples

Example 1

Input: nums = [1,2,3]

Output: 2

We can decrease 2 to 0 or 3 to 1.

Example 2

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

Output: 4

Example details omitted.

Constraints

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

Solution Approach

Separate Even and Odd Peaks

Treat the two possible zigzag patterns independently: first assume even indices are peaks, then assume odd indices are peaks. This ensures that each pattern's invariant is validated without interference from the other.

Greedy Decrease Strategy

Iterate through the array and for each element at the chosen peak positions, decrease it just enough so it is greater than its neighbors. This minimizes unnecessary moves and guarantees correctness for each local decision.

Compare and Return Minimum Moves

After calculating the total moves required for both even-peak and odd-peak scenarios, compare the totals and return the smaller value. This ensures the global minimal move count while adhering to the greedy invariant logic.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is visited twice (once per pattern) with constant-time calculations. Space complexity is O(1) since calculations are done in-place without extra structures beyond counters.

What Interviewers Usually Probe

Candidate separates even and odd index patterns without merging logic.
Candidate applies minimal necessary decrements to satisfy local zigzag conditions.
Candidate correctly returns the smaller move count between two independent patterns.

Common Pitfalls or Variants

Common pitfalls

Decreasing elements more than needed, inflating the move count.
Only checking one index pattern and missing the globally minimal solution.
Failing to correctly handle edge neighbors at array boundaries.

Follow-up variants

Compute zigzag moves where only adjacent differences matter, not absolute values.
Allow increases as well as decreases to achieve zigzag minimal moves.
Handle circular arrays where first and last elements are neighbors.

FAQ

What is the best approach to solve Decrease Elements To Make Array Zigzag?

Use a greedy strategy considering both even-index and odd-index peaks separately, decreasing elements just enough to satisfy the local zigzag condition.

How does the invariant guide the greedy choices?

The invariant ensures each peak element is strictly greater than neighbors, so greedy decreases only occur when this condition is violated.

Can I solve this with only one pass through the array?

Not safely; you need to evaluate both even-peak and odd-peak scenarios independently to guarantee minimal moves.

What is the time complexity for this problem?

Time complexity is O(n) because each element is processed for both index patterns, and space complexity is O(1) for counters.

Are there variations of this problem to consider?

Yes, including allowing increases, handling circular arrays, or only considering adjacent differences instead of absolute values.

terminal

Solution

Solution 1: Enumeration + Greedy

We can separately enumerate the even and odd positions as the elements "smaller than adjacent elements", and then calculate the required number of operations. The minimum of the two is taken.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        ans = [0, 0]
        n = len(nums)
        for i in range(2):
            for j in range(i, n, 2):
                d = 0
                if j:
                    d = max(d, nums[j] - nums[j - 1] + 1)
                if j < n - 1:
                    d = max(d, nums[j] - nums[j + 1] + 1)
                ans[i] += d
        return min(ans)

Continue Practicing

#1130 minimum cost tree from leaf values #1090 largest values from labels #1217 minimum cost to move chips to the same position