Decrease Elements To Make Array Zigzag solution and explanation
Google
4 more videos on this problem
Decrease Elements To Make Array Zigzag (Leetcode 1144)Coding Interviews · 22:13 · 1K views
LeeCode 1144. Decrease Elements To Make Array ZigzagcoderZ · 13:05 · 670 views
米开：LeetCode 1144. Decrease Elements To Make Array ZigzagM.C米开朗基罗 · 8:35 · 339 views
No Sound Leetcode 1144: Decrease Elements to Make Array ZigzagExtremeProgrammer · 3:22 · 22 views
LeetCode 1144: Decrease Elements To Make Array ZigzagAlitaCode · 28:31 · 12 views
The problem
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.
def min_moves_to_make_zigzag(nums):
def moves(idx):
result = 0
for i in range(idx, len(nums), 2):
left = nums[i - 1] if i > 0 else float('inf')
right = nums[i + 1] if i + 1 < len(nums) else float('inf')
min_neigh = min(left, right)
if nums[i] >= min_neigh:
result += nums[i] - min_neigh + 1
return result
return min(moves(0), moves(1))
if __name__ == '__main__':
nums = [9, 6, 1, 6, 2]
print(min_moves_to_make_zigzag(nums))import java.util.*;
class Solution {
public int minMovesToMakeZigzag(int[] nums) {
return Math.min(moves(nums, 0), moves(nums, 1));
}
private int moves(int[] nums, int idx) {
int result = 0;
for (int i = idx; i < nums.length; i += 2) {
int left = i > 0 ? nums[i - 1] : Integer.MAX_VALUE;
int right = i + 1 < nums.length ? nums[i + 1] : Integer.MAX_VALUE;
int minNeigh = Math.min(left, right);
if (nums[i] >= minNeigh) {
result += nums[i] - minNeigh + 1;
}
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {9, 6, 1, 6, 2};
System.out.println(solution.minMovesToMakeZigzag(nums));
}
}#include <vector>
#include <algorithm>
#include <limits>
class Solution {
public:
int minMovesToMakeZigzag(std::vector<int>& nums) {
return std::min(moves(nums, 0), moves(nums, 1));
}
int moves(std::vector<int>& nums, int start) {
int result = 0;
for (int i = start; i < nums.size(); i += 2) {
int left = (i > 0 ? nums[i - 1] : std::numeric_limits<int>::max());
int right = (i + 1 < nums.size() ? nums[i + 1] : std::numeric_limits<int>::max());
int min_neighbor = std::min(left, right);
if (nums[i] >= min_neighbor) {
result += nums[i] - min_neighbor + 1;
}
}
return result;
}
};
int main() {
Solution solution;
std::vector<int> nums = {9, 6, 1, 6, 2};
int result = solution.minMovesToMakeZigzag(nums);
std::cout << result << std::endl;
return 0;
}var minMovesToMakeZigzag = function(nums) {
const moves = (idx) => {
let result = 0;
for (let i = idx; i < nums.length; i += 2) {
let left = i > 0 ? nums[i - 1] : Infinity;
let right = i + 1 < nums.length ? nums[i + 1] : Infinity;
let minNeigh = Math.min(left, right);
if (nums[i] >= minNeigh) {
result += nums[i] - minNeigh + 1;
}
}
return result;
};
return Math.min(moves(0), moves(1));
};
console.log(minMovesToMakeZigzag([9, 6, 1, 6, 2]));#include <stdio.h>
#include <limits.h>
int minMoves(int* nums, int numsSize) {
int moves1 = 0, moves2 = 0;
for (int i = 0; i < numsSize; i++) {
int left = (i > 0) ? nums[i - 1] : INT_MAX;
int right = (i < numsSize - 1) ? nums[i + 1] : INT_MAX;
if (i % 2 == 0) {
int decrease = nums[i] - ((left < right ? left : right) - 1);
moves1 += (decrease > 0 ? decrease : 0);
} else {
int decrease = nums[i] - ((left < right ? left : right) - 1);
moves2 += (decrease > 0 ? decrease : 0);
}
}
return moves1 < moves2 ? moves1 : moves2;
}
int main() {
int nums[] = {9, 6, 1, 6, 2};
int result = minMoves(nums, 5);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int MinMovesToMakeZigzag(int[] nums) {
return Math.Min(Moves(nums, 0), Moves(nums, 1));
}
private int Moves(int[] nums, int idx) {
int result = 0;
for (int i = idx; i < nums.Length; i += 2) {
int left = i > 0 ? nums[i - 1] : int.MaxValue;
int right = i + 1 < nums.Length ? nums[i + 1] : int.MaxValue;
int minNeigh = Math.Min(left, right);
if (nums[i] >= minNeigh) {
result += nums[i] - minNeigh + 1;
}
}
return result;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {9, 6, 1, 6, 2};
Console.WriteLine(solution.MinMovesToMakeZigzag(nums));
}
}In Python, we define a helper function 'moves' inside the main function that computes the required decreases. It calculates the necessary decreases to achieve both patterns and returns the minimum.
Time Complexity: O(n), where n is the length of the input list.
Space Complexity: O(1), with very limited additional space used.
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).
function movesToMakeZigzag(nums: number[]): number {
const ans: number[] = Array(2).fill(0);
const n = nums.length;
for (let i = 0; i < 2; ++i) {
for (let j = i; j < n; j += 2) {
let d = 0;
if (j > 0) {
d = Math.max(d, nums[j] - nums[j - 1] + 1);
}
if (j < n - 1) {
d = Math.max(d, nums[j] - nums[j + 1] + 1);
}
ans[i] += d;
}
}
return Math.min(...ans);
}func movesToMakeZigzag(nums []int) int {
ans := [2]int{}
n := len(nums)
for i := 0; i < 2; i++ {
for j := i; j < n; j += 2 {
d := 0
if j > 0 {
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[0], ans[1])
}Complexity comparison
| Approach | Complexity |
|---|---|
| Pattern-Based Adjustment | Time Complexity: O(n), where n is the length of the input list. |
| Enumeration + Greedy | – |
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. |
Frequently asked questions
Is Decrease Elements To Make Array Zigzag easy or hard?
Decrease Elements To Make Array Zigzag is classified as Medium difficulty. The implementation is straightforward once you recognize that two zigzag patterns must be evaluated. The main challenge is identifying the greedy insight that only valley positions need to be decreased.
Decrease Elements To Make Array Zigzag Python/Java solution
In Python or Java, implement a loop that calculates the decrement cost for each index based on the minimum of its neighbors. Run the calculation twice: once assuming even indices are valleys and once assuming odd indices are valleys. Return the minimum of the two totals. The implementation uses simple array access and integer arithmetic.
How to solve Decrease Elements To Make Array Zigzag in O(n)?
Compute the cost of making even indices valleys and the cost of making odd indices valleys. For each index, check the minimum of its adjacent elements and determine how much the current value must be decreased to be strictly smaller. Accumulate the required decrements and return the smaller total. This requires two linear passes, giving O(n) time and constant extra space.
What is the best approach for Decrease Elements To Make Array Zigzag?
The best approach is a greedy pattern-based adjustment. Evaluate two possible zigzag configurations: even indices as valleys or odd indices as valleys. For each index, compute the number of decrements needed to make it smaller than its neighbors. Summing these costs for each pattern and returning the minimum gives an O(n) time and O(1) space solution.
Is Decrease Elements To Make Array Zigzag asked at Google/Amazon/Meta?
This problem reflects common interview themes used by companies like Google, Amazon, and Meta: greedy reasoning and local constraint optimization on arrays. While the exact question may vary, similar zigzag or alternating pattern problems frequently appear in coding interviews.
What data structure is used in Decrease Elements To Make Array Zigzag?
The solution primarily uses a simple array traversal with constant extra variables. No advanced data structures are required. The logic relies on comparing each element with its immediate neighbors and applying a greedy adjustment strategy.
What is the time complexity of Decrease Elements To Make Array Zigzag?
The optimal solution runs in O(n) time because the array is scanned twice—once for each possible zigzag pattern. Each step performs constant-time comparisons with neighboring elements. The space complexity is O(1) since only counters and temporary values are used.