Decrease Elements To Make Array Zigzag - Solution & Explanation
Problem Statement
Given an array nums of integers, a move consists of choosing any element and decreasing it by 1.
An array A is a zigzag array if either:
- Every even-indexed element is greater than adjacent elements, ie.
A[0] > A[1] < A[2] > A[3] < A[4] > ... - OR, every odd-indexed element is greater than adjacent elements, ie.
A[0] < A[1] > A[2] < A[3] > A[4] < ...
Return the minimum number of moves to transform the given array nums into a zigzag array.
Example 1:
Input: nums = [1,2,3] Output: 2 Explanation: We can decrease 2 to 0 or 3 to 1.
Example 2:
Input: nums = [9,6,1,6,2] Output: 4
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 1000
Approach Overview
Problem Overview: You’re given an integer array and can only decrease values. The goal is to transform the array into a zigzag pattern with the minimum number of decrement operations. A zigzag array means either nums[0] < nums[1] > nums[2] < nums[3]... or nums[0] > nums[1] < nums[2] > nums[3].... The task is to compute the minimum total decrements required to achieve either pattern.
Approach 1: Brute Force Neighbor Adjustment (O(n), O(1))
Check both valid zigzag configurations separately. For one pass, enforce that even indices are valleys (nums[i] < nums[i-1] and nums[i] < nums[i+1]), and for the other pass enforce the same rule for odd indices. For each index, compare the value with its neighbors and calculate how much it must be decreased to become strictly smaller than the minimum neighbor. Accumulate the required decrements without modifying the original array. This works because decreasing one element never breaks the constraint for other indices when evaluated independently.
Approach 2: Pattern-Based Greedy Adjustment (O(n), O(1))
This is the optimal greedy strategy. Instead of modifying the array, compute the cost of making each index the "valley" of the zigzag pattern. For index i, find the smallest neighbor among nums[i-1] and nums[i+1]. If nums[i] is not already smaller, calculate the decrements required to make it minNeighbor - 1. Sum these costs for all indices of the same parity (even or odd). Since a valid zigzag can start with either a peak or valley, run this calculation twice: once assuming even indices are valleys and once assuming odd indices are valleys. Return the smaller cost. The algorithm scans the array once per pattern and uses only constant extra memory, making it efficient for large inputs.
The core insight: only the valley positions need adjustment. Peaks automatically satisfy the constraint if their neighboring valleys are smaller. By computing the minimal decrement needed relative to neighbors, the algorithm avoids unnecessary changes and keeps the solution linear.
This problem is a good exercise in recognizing local constraints in array problems and applying a simple greedy decision at each index.
Recommended for interviews: The pattern-based greedy approach is what interviewers expect. It shows you can reason about local constraints and reduce the problem to two deterministic passes. Explaining both zigzag patterns first demonstrates complete understanding, then implementing the O(n) greedy calculation shows practical problem-solving skill.
Approach 1: Pattern-Based Adjustment
This approach considers two patterns for the zigzag sequence: even-indexed elements being greater than their neighbors and odd-indexed elements being greater than their neighbors. We calculate the moves necessary to transition to both patterns and return the minimum of these values as the result.
In this solution, we iterate over the array twice. Once, considering adjustments for the pattern where even-indexed elements are greater, and once for the pattern where odd-indexed elements are greater. We calculate the moves required to make each element less than its neighbors if it's in the non-leading position of the pattern. We return the minimum of the two counts of moves.
Complexity
Time Complexity: O(n), where n is the number of elements in the array. We perform a constant-time operation for each element.
Space Complexity: O(1), since we use a fixed amount of extra memory.
Approach 2: 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.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Pattern-Based Adjustment | Time Complexity: O(n), where n is the number of elements in the array. We perform a constant-time operation for each element. |
| Enumeration + Greedy | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Neighbor Adjustment | O(n) | O(1) | Good for reasoning about the zigzag condition and validating both possible patterns. |
| Pattern-Based Greedy Adjustment | O(n) | O(1) | Best choice for interviews and production. Computes minimal decrements in two linear scans. |
Video Solution
Decrease Elements To Make Array Zigzag (Leetcode 1144) • Coding Interviews • 1,824 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Decrease Elements To Make Array Zigzag easy or hard?
Decrease Elements To Make Array Zigzag Python/Java solution
How to solve Decrease Elements To Make Array Zigzag in O(n)?
What is the best approach for Decrease Elements To Make Array Zigzag?
Is Decrease Elements To Make Array Zigzag asked at Google/Amazon/Meta?
What data structure is used in Decrease Elements To Make Array Zigzag?
What is the time complexity of Decrease Elements To Make Array Zigzag?
Ready to solve this problem?
Practice Decrease Elements To Make Array Zigzag with our built-in code editor and test cases.
Practice on FleetCode