Here’s the question link on LeetCode 1144 Decrease Elements To Make Array Zigzag:
https://leetcode.com/problems/decrease-elements-to-make-array-zigzag/description
Contents
Brute Force – O(n × max(nums))
We have two choices:
Choice 1: Make even indices smaller than their neighbors.
[1, 4, 2, 5, 1]
Choice 2: Make odd indices smaller than their neighbors.
[4, 1, 5, 2, 6]
Let’s try both!
For every index that needs to be smaller, keep decreasing it until it’s smaller than both its neighbors.
For example:
[3, 2, 4]
If we want the middle element to be smaller:
[3, 2, 4]
[3, 1, 4]
Just one move!
We do this for both patterns and return whichever requires fewer moves.
class Solution {
public:
int simulate(vector<int> nums, int parity) {
int moves = 0;
int n = nums.size();
for(int i = parity; i < n; i += 2) {
while((i > 0 && nums[i] >= nums[i-1]) ||
(i < n-1 && nums[i] >= nums[i+1])) {
nums[i]--;
moves++;
}
}
return moves;
}
int movesToMakeZigzag(vector<int>& nums) {
return min(simulate(nums, 0), simulate(nums, 1));
}
};
Code explained
simulate(nums, 0)tries making even indices smaller.simulate(nums, 1)tries making odd indices smaller.- Keep decreasing the selected element until it’s smaller than both neighbors.
- Count the moves and return the minimum of both attempts.
Optimal – O(n)
Wait, why are we decreasing elements one by one?
We can directly calculate how many times we need to decrease an element!
Let’s say:
[3, 5, 4]
We want the middle element to be smaller than both neighbors.
Currently, it’s 5.
The smaller neighbor is 3.
So the middle element must become 2.
[3, 2, 4]
That’s exactly 5 - 3 + 1 = 3 moves!
The formula:
max(0, nums[i] - min(left, right) + 1)
Why +1? Because we need the element to be strictly smaller than its neighbors.
Now we just calculate this cost for every even index and every odd index separately.
class Solution {
public:
int movesToMakeZigzag(vector<int>& nums) {
int n = nums.size();
int even = 0, odd = 0;
for(int i = 0; i < n; i++) {
int left = (i > 0) ? nums[i-1] : INT_MAX;
int right = (i < n-1) ? nums[i+1] : INT_MAX;
int cost = max(0, nums[i] - min(left, right) + 1);
if(i % 2 == 0)
even += cost;
else
odd += cost;
}
return min(even, odd);
}
};
Code explained
evenstores the moves needed if even indices must be smaller.oddstores the moves needed if odd indices must be smaller.- Find the smaller of the two neighbors.
- Calculate how many decrements are needed to become smaller than that neighbor.
- Add the cost to either
evenorodd. - Return whichever pattern costs less.
We use INT_MAX for a missing neighbor because boundary elements only have one neighbor.