LeetCode 1144 - Decrease Elements To Make Array Zigzag

The problem gives an integer array nums and allows only one type of operation, decreasing any element by 1. We may perform this operation as many times as needed on any elements. Our goal is to transform the array into a zigzag array with the minimum number of moves.

leetcodemediumarraygreedy

LeetCode Problem 1144

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives an integer array nums and allows only one type of operation, decreasing any element by 1. We may perform this operation as many times as needed on any elements.

Our goal is to transform the array into a zigzag array with the minimum number of moves.

A zigzag array can follow one of two valid patterns:

  1. Even indices are peaks:

nums[0] > nums[1] < nums[2] > nums[3] < nums[4] ... 2. Odd indices are peaks:

nums[0] < nums[1] > nums[2] < nums[3] > nums[4] ...

We are free to choose whichever pattern requires fewer total decreases.

The important detail is that we are only allowed to decrease values. Increasing an element is never allowed. This restriction completely changes the strategy because if an element is too small relative to its neighbors, we cannot raise it, we must instead reduce surrounding values.

The input size is relatively small:

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

These constraints tell us that even an O(n^2) solution would likely pass, but we should still aim for a clean linear solution.

A key observation is that every position only depends on its immediate neighbors. Whether an element satisfies the zigzag requirement can be determined locally by comparing it with adjacent values.

Several edge cases are important:

  • Arrays of length 1 are already zigzag arrays because there are no adjacent elements to violate the pattern.
  • Arrays with equal neighboring values require reductions because strict inequalities are required.
  • Boundary elements only have one neighbor, so comparisons must handle missing left or right neighbors carefully.
  • Large values are harmless because we only perform arithmetic differences.

Approaches

Brute Force Approach

A brute force strategy would attempt to simulate both zigzag patterns by repeatedly adjusting elements until all inequalities are satisfied.

For example, we could repeatedly scan the array and whenever a position violates the zigzag condition, decrease the offending element until the condition becomes valid. We would do this separately for:

  • even indices as peaks
  • odd indices as peaks

This eventually produces a valid zigzag array because decreasing values can always fix violations.

However, this approach is inefficient because repeatedly decrementing elements one step at a time may require many operations. Since values can be as large as 1000, the simulation may perform unnecessary repeated work.

The key inefficiency is that we do not actually need to simulate each decrement individually. We can directly compute how many decreases are required for each position.

Optimal Greedy Approach

The important insight is that each position can be handled independently once we decide which parity should contain the valleys.

Suppose we want index i to be a valley. Then it must satisfy:

nums[i] < left neighbor
nums[i] < right neighbor

Because we are only allowed to decrease values, the only way to guarantee this is to reduce nums[i] itself.

To make nums[i] strictly smaller than both neighbors, its maximum allowed value becomes:

min(left neighbor, right neighbor) - 1

If nums[i] is already smaller than both neighbors, no work is needed.

Otherwise, the required decreases are:

nums[i] - (minNeighbor - 1)

We compute this independently for every valley position.

We evaluate two scenarios:

  1. Even indices are valleys
  2. Odd indices are valleys

The minimum total cost of the two scenarios is the answer.

This works because each valley adjustment is local and does not interfere with other valleys.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * max(nums)) O(1) Simulates decrements repeatedly
Optimal O(n) O(1) Directly computes required reductions

Algorithm Walkthrough

  1. Create a helper function that computes the total moves needed when a chosen parity represents valley positions.
  2. For every index i with the selected parity:
  • Find the left neighbor if it exists.
  • Find the right neighbor if it exists.
  • Compute the minimum neighbor value.
  1. Since the current element must become strictly smaller than both neighbors, the largest valid value is:
minNeighbor - 1
  1. If nums[i] is already smaller than both neighbors, no moves are required.
  2. Otherwise, calculate how many decrements are needed:
nums[i] - (minNeighbor - 1)
  1. Add this value to the running total.
  2. Repeat for all valley positions.
  3. Run the helper twice:
  • once with even indices as valleys
  • once with odd indices as valleys
  1. Return the smaller result.

Why it works

For any valid zigzag configuration, one parity must contain all valleys. A valley only needs to be smaller than its adjacent neighbors, so its required adjustment depends solely on local comparisons.

Because decreasing one valley does not invalidate another valley requirement, each position can be optimized independently. Computing the minimum necessary reduction for every valley therefore produces the globally minimum number of moves.

Python Solution

from typing import List

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        n = len(nums)

        def calculate_moves(valley_parity: int) -> int:
            moves = 0

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

                min_neighbor = min(left, right)

                needed = max(0, nums[i] - (min_neighbor - 1))
                moves += needed

            return moves

        return min(calculate_moves(0), calculate_moves(1))

The implementation follows the greedy observation directly.

The helper function calculate_moves evaluates one zigzag configuration. The parameter valley_parity determines which indices should become valleys.

For each valley position, the code retrieves the left and right neighbors. Missing neighbors are treated as positive infinity so boundary elements only compare against the neighbor that actually exists.

The smallest neighboring value determines the maximum legal value for the current element. If the current element is already valid, max(0, ...) ensures no unnecessary moves are added.

Finally, the algorithm computes the total cost for both possible zigzag patterns and returns the smaller one.

Go Solution

func movesToMakeZigzag(nums []int) int {
	n := len(nums)

	calculateMoves := func(valleyParity int) int {
		moves := 0

		for i := valleyParity; i < n; i += 2 {
			left := 1 << 30
			right := 1 << 30

			if i > 0 {
				left = nums[i-1]
			}

			if i+1 < n {
				right = nums[i+1]
			}

			minNeighbor := left
			if right < minNeighbor {
				minNeighbor = right
			}

			needed := nums[i] - (minNeighbor - 1)
			if needed > 0 {
				moves += needed
			}
		}

		return moves
	}

	evenValleys := calculateMoves(0)
	oddValleys := calculateMoves(1)

	if evenValleys < oddValleys {
		return evenValleys
	}

	return oddValleys
}

The Go implementation mirrors the Python logic closely.

Since Go does not have a built in infinity value for integers, a very large number (1 << 30) is used for missing neighbors.

The rest of the logic remains identical:

  • evaluate both parity configurations
  • compute required reductions locally
  • return the minimum total moves

Integer overflow is not a concern because all values remain small under the problem constraints.

Worked Examples

Example 1

Input:

nums = [1, 2, 3]

We test both zigzag patterns.

Case 1: Even indices are valleys

Target pattern:

1 < 2 > 3

Valley indices: 0, 2

Index Value Neighbors Min Neighbor Moves Needed
0 1 2 2 0
2 3 2 2 2

Total moves = 2

After decreasing:

[1, 2, 1]

Case 2: Odd indices are valleys

Target pattern:

1 > 2 < 3

Valley indices: 1

Index Value Neighbors Min Neighbor Moves Needed
1 2 1, 3 1 2

Total moves = 2

Minimum answer:

2

Example 2

Input:

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

Case 1: Even indices are valleys

Valley indices: 0, 2, 4

Index Value Neighbors Min Neighbor Moves Needed
0 9 6 6 4
2 1 6, 6 6 0
4 2 6 6 0

Total = 4

Case 2: Odd indices are valleys

Valley indices: 1, 3

Index Value Neighbors Min Neighbor Moves Needed
1 6 9, 1 1 6
3 6 1, 2 1 6

Total = 12

Minimum answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed at most twice
Space O(1) Only constant extra variables are used

The algorithm performs two linear scans of the array, one for each zigzag pattern. Each scan processes every other element and performs only constant time operations.

No auxiliary data structures proportional to input size are required, so the space usage remains constant.

Test Cases

from typing import List

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        n = len(nums)

        def calculate_moves(valley_parity: int) -> int:
            moves = 0

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

                min_neighbor = min(left, right)
                moves += max(0, nums[i] - (min_neighbor - 1))

            return moves

        return min(calculate_moves(0), calculate_moves(1))

sol = Solution()

assert sol.movesToMakeZigzag([1, 2, 3]) == 2  # provided example
assert sol.movesToMakeZigzag([9, 6, 1, 6, 2]) == 4  # provided example

assert sol.movesToMakeZigzag([1]) == 0  # single element already zigzag
assert sol.movesToMakeZigzag([2, 1]) == 0  # already zigzag
assert sol.movesToMakeZigzag([1, 2]) == 0  # already zigzag in opposite pattern

assert sol.movesToMakeZigzag([2, 2, 2]) == 2  # equal neighboring values
assert sol.movesToMakeZigzag([5, 5, 5, 5]) == 2  # repeated values

assert sol.movesToMakeZigzag([10, 10, 10]) == 1  # one reduction sufficient
assert sol.movesToMakeZigzag([3, 4, 5, 6]) == 4  # increasing sequence
assert sol.movesToMakeZigzag([6, 5, 4, 3]) == 4  # decreasing sequence

assert sol.movesToMakeZigzag([1, 3, 1, 3, 1]) == 0  # already zigzag
assert sol.movesToMakeZigzag([1000, 1, 1000]) == 0  # large values already valid
Test Why
[1,2,3] Validates the basic example
[9,6,1,6,2] Validates alternating reductions
[1] Tests minimum array size
[2,1] Tests already valid decreasing pair
[1,2] Tests already valid increasing pair
[2,2,2] Tests strict inequality handling
[5,5,5,5] Tests repeated equal values
[10,10,10] Tests minimal reduction computation
[3,4,5,6] Tests monotonic increasing array
[6,5,4,3] Tests monotonic decreasing array
[1,3,1,3,1] Tests already zigzag pattern
[1000,1,1000] Tests upper value range

Edge Cases

One important edge case is an array with only one element. Since there are no adjacent elements, the array automatically satisfies both zigzag definitions. A careless implementation might attempt invalid neighbor access. This solution safely handles the case because missing neighbors are treated as infinity.

Another important case is arrays containing equal adjacent values, such as [2,2,2]. The zigzag requirement uses strict inequalities, so equality is not allowed. The implementation correctly computes how many decrements are needed to make one side strictly smaller by using minNeighbor - 1.

Boundary positions are also easy to mishandle because they only have one neighbor instead of two. For example, index 0 has no left neighbor and the last index has no right neighbor. The algorithm handles this cleanly by assigning nonexistent neighbors an infinite value, ensuring only real neighbors affect the reduction calculation.