Problem Description

You are given an array nums of integers. In one move, you can choose any element and decrease it by 1.

A zigzag array is an array that satisfies one of these two patterns:

1. Even-indexed elements are peaks: Every element at an even index is greater than its adjacent elements. This creates a pattern like: A[0] > A[1] < A[2] > A[3] < A[4] > ...

2. Odd-indexed elements are peaks: Every element at an odd index is greater than its adjacent elements. This creates a pattern like: A[0] < A[1] > A[2] < A[3] > A[4] < ...

Your task is to find the minimum number of moves needed to transform the given array into a zigzag array.

For example, if nums = [1, 2, 3]:

• To make even-indexed elements peaks: We need nums[0] > nums[1] and nums[2] > nums[1]. The array [1, 0, 3] works, requiring 2 moves (decreasing nums[1] by 2).
• To make odd-indexed elements peaks: We need nums[1] > nums[0] and nums[1] > nums[2]. The array [1, 2, 1] works, requiring 2 moves (decreasing nums[2] by 2).
• The minimum is 2 moves.

The solution considers both possible zigzag patterns and calculates the cost for each. For each pattern, it iterates through positions that should be "valleys" (smaller than neighbors) and calculates how much to decrease them to satisfy the zigzag property. The answer is the minimum cost between the two patterns.

Intuition

The key insight is that we can only decrease elements, never increase them. This constraint actually simplifies our problem significantly.

Since we want to create a zigzag pattern, we have exactly two choices:

1. Make elements at even indices the "peaks" (larger than neighbors)
2. Make elements at odd indices the "peaks" (larger than neighbors)

Here's the crucial observation: if we decide which positions should be peaks, then the other positions must be "valleys" (smaller than neighbors). Since we can only decrease values, the peaks should remain unchanged - we achieve the zigzag pattern by lowering the valleys.

For any valley position, we need to ensure it's smaller than both its neighbors. If the current value at a valley position is nums[j], and its neighbors are nums[j-1] and nums[j+1], then we need:

• nums[j] < nums[j-1], which means we need to decrease by at least nums[j] - nums[j-1] + 1 if nums[j] >= nums[j-1]
• nums[j] < nums[j+1], which means we need to decrease by at least nums[j] - nums[j+1] + 1 if nums[j] >= nums[j+1]

We take the maximum of these requirements to satisfy both conditions simultaneously.

The greedy approach works because:

1. We never need to decrease peak positions (doing so would only make things harder)
2. For each valley, we decrease it by the minimum amount necessary to be smaller than its neighbors
3. Each position's adjustment is independent - lowering one valley doesn't affect the requirements for other valleys

By calculating the total cost for both patterns (even peaks vs odd peaks) and taking the minimum, we find the optimal solution.

Learn more about Greedy patterns.

Solution Approach

The implementation uses enumeration and greedy strategy to find the minimum moves needed.

We maintain an array ans = [0, 0] where:

• ans[0] stores the total moves needed when even-indexed elements are valleys
• ans[1] stores the total moves needed when odd-indexed elements are valleys

The outer loop for i in range(2) handles both patterns:

• When i = 0: We process even indices (0, 2, 4, ...) as valleys
• When i = 1: We process odd indices (1, 3, 5, ...) as valleys

For each pattern, we iterate through the valley positions using for j in range(i, n, 2). This clever iteration starts at index i and jumps by 2 each time, visiting all positions that should be valleys.

At each valley position j, we calculate the required decrease amount d:

1. Left neighbor check: If j > 0, we need nums[j] < nums[j-1]. If currently nums[j] >= nums[j-1], we must decrease by at least nums[j] - nums[j-1] + 1. We update d = max(d, nums[j] - nums[j-1] + 1).

2. Right neighbor check: If j < n - 1, we need nums[j] < nums[j+1]. If currently nums[j] >= nums[j+1], we must decrease by at least nums[j] - nums[j+1] + 1. We update d = max(d, nums[j] - nums[j+1] + 1).

The max operation ensures we decrease enough to be smaller than both neighbors. If d remains 0, it means the current element is already smaller than its neighbors, requiring no moves.

We accumulate the total moves for each pattern: ans[i] += d.

Finally, we return min(ans) to get the minimum moves between the two possible zigzag patterns.

The time complexity is O(n) as we visit each element at most twice, and space complexity is O(1) using only constant extra space.

Example Walkthrough

Let's walk through the example nums = [2, 7, 10, 9, 8, 9] to illustrate the solution approach.

Pattern 1: Even indices as valleys (positions 0, 2, 4 should be smaller than neighbors)

• Position 0 (value = 2):

  • No left neighbor
  • Right neighbor at position 1 has value 7
  • Need: nums[0] < nums[1] → 2 < 7 ✓ Already satisfied
  • Decrease needed: 0

• Position 2 (value = 10):

  • Left neighbor at position 1 has value 7
  • Right neighbor at position 3 has value 9
  • Need: nums[2] < nums[1] → 10 < 7 ✗ Must decrease by 10 - 7 + 1 = 4
  • Need: nums[2] < nums[3] → 10 < 9 ✗ Must decrease by 10 - 9 + 1 = 2
  • Decrease needed: max(4, 2) = 4

• Position 4 (value = 8):

  • Left neighbor at position 3 has value 9
  • Right neighbor at position 5 has value 9
  • Need: nums[4] < nums[3] → 8 < 9 ✓ Already satisfied
  • Need: nums[4] < nums[5] → 8 < 9 ✓ Already satisfied
  • Decrease needed: 0

Total moves for Pattern 1: 0 + 4 + 0 = 4 Result: [2, 7, 6, 9, 8, 9] (peak-valley-peak-valley-peak pattern)

Pattern 2: Odd indices as valleys (positions 1, 3, 5 should be smaller than neighbors)

• Position 1 (value = 7):

  • Left neighbor at position 0 has value 2
  • Right neighbor at position 2 has value 10
  • Need: nums[1] < nums[0] → 7 < 2 ✗ Must decrease by 7 - 2 + 1 = 6
  • Need: nums[1] < nums[2] → 7 < 10 ✓ Already satisfied
  • Decrease needed: max(6, 0) = 6

• Position 3 (value = 9):

  • Left neighbor at position 2 has value 10
  • Right neighbor at position 4 has value 8
  • Need: nums[3] < nums[2] → 9 < 10 ✓ Already satisfied
  • Need: nums[3] < nums[4] → 9 < 8 ✗ Must decrease by 9 - 8 + 1 = 2
  • Decrease needed: max(0, 2) = 2

• Position 5 (value = 9):

  • Left neighbor at position 4 has value 8
  • No right neighbor
  • Need: nums[5] < nums[4] → 9 < 8 ✗ Must decrease by 9 - 8 + 1 = 2
  • Decrease needed: 2

Total moves for Pattern 2: 6 + 2 + 2 = 10 Result: [2, 1, 10, 7, 8, 7] (valley-peak-valley-peak-valley pattern)

Final Answer: min(4, 10) = 4 moves

The optimal solution transforms the array to [2, 7, 6, 9, 8, 9] using 4 moves by making even indices valleys.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm uses two nested loops where the outer loop runs exactly 2 iterations (for i in range(2)), and the inner loop iterates through the array with step size 2. For each value of i, the inner loop visits approximately n/2 elements. Therefore, the total number of operations is 2 * (n/2) = n, resulting in linear time complexity.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space: the list ans with exactly 2 elements, and a few integer variables (n, i, j, d). The space usage does not grow with the input size, making it constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding Which Elements to Modify

A critical pitfall is misunderstanding which elements should be decreased. The code appears to decrease elements at "peak" positions, but it's actually decreasing elements at "valley" positions.

The Bug: The variable naming and comments are misleading. When pattern_type = 0, we're actually processing even indices as valleys (not peaks), meaning we want even indices to be smaller than their neighbors.

Incorrect Understanding:

# Wrong interpretation: "Making even indices peaks"
for peak_index in range(pattern_type, n, 2):  # Misleading name!
    decrease_amount = 0
    # This logic actually ensures current element becomes SMALLER than neighbors

Correct Understanding:

# Correct: Making even indices valleys (odd indices become peaks)
for valley_index in range(pattern_type, n, 2):
    decrease_needed = 0
    # Ensure valley is smaller than both neighbors
    if valley_index > 0:
        # Need: nums[valley] < nums[valley-1]
        if nums[valley_index] >= nums[valley_index - 1]:
            decrease_needed = max(decrease_needed, nums[valley_index] - nums[valley_index - 1] + 1)

2. Incorrect Decrease Calculation

Another pitfall is calculating the wrong decrease amount. The code calculates how much to decrease the current element to be smaller than neighbors, not how much to decrease the neighbors.

Example to Illustrate:

• Array: [2, 5, 3]
• To make index 1 a valley: We need nums[1] < nums[0] and nums[1] < nums[2]
• Current: nums[1] = 5, nums[0] = 2, nums[2] = 3
• Decrease needed: max(5 - 2 + 1, 5 - 3 + 1) = max(4, 3) = 4
• Result: Decrease nums[1] by 4 to get [2, 1, 3]

3. Pattern Confusion

The two patterns being tested are:

• Pattern 0: Even indices are valleys → Odd indices are peaks → [small, LARGE, small, LARGE, ...]
• Pattern 1: Odd indices are valleys → Even indices are peaks → [LARGE, small, LARGE, small, ...]

Corrected Solution with Clear Naming:

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        """
        Find minimum moves to make array zigzag pattern.
        Two possible patterns:
        1. Even valleys: nums[0] < nums[1] > nums[2] < nums[3] > ...
        2. Odd valleys:  nums[0] > nums[1] < nums[2] > nums[3] < ...
        """
        moves = [0, 0]  # [moves for even valleys, moves for odd valleys]
        n = len(nums)
      
        for pattern in range(2):
            # pattern=0: make even indices valleys (odd indices peaks)
            # pattern=1: make odd indices valleys (even indices peaks)
            for valley_idx in range(pattern, n, 2):
                decrease = 0
              
                # Check if valley needs to be smaller than left neighbor
                if valley_idx > 0 and nums[valley_idx] >= nums[valley_idx - 1]:
                    decrease = max(decrease, nums[valley_idx] - nums[valley_idx - 1] + 1)
              
                # Check if valley needs to be smaller than right neighbor
                if valley_idx < n - 1 and nums[valley_idx] >= nums[valley_idx + 1]:
                    decrease = max(decrease, nums[valley_idx] - nums[valley_idx + 1] + 1)
              
                moves[pattern] += decrease
      
        return min(moves)

The key insight is that we're always decreasing elements at valley positions to ensure they're strictly smaller than their neighbors, not making peaks higher.