# Decrease Elements To Make Array Zigzag LeetCode Solution

Difficulty Level Medium

## Problem Statement :

Decrease Elements To Make Array Zigzag LeetCode Solution – 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 > A < A > A < A > …
• OR, every odd-indexed element is greater than adjacent elements, ie. A < A > A < A > A < …

Return the minimum number of moves to transform the given array nums into a zigzag array.

## Example :

### 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 : ## Intuition :

• There are only 2 ways to make the array zigzag, either take all the odd elements and make them smaller than their neighbors, or take all the even elements and make them smaller than their neighbors.
• We are greedily looking for our answer, so we will use the Greedy algorithm.

## Algorithm :

• we will first make every element at an even index smaller than it’s adjacent and count the steps to make it smaller.
• we will then make every element at an odd index smaller than its adjacent and count the steps to make it smaller.
• We will use two loops, one for the odd index and the other for the even index.
• While iterating we will check if the current index is not smaller than its adjacent then we will take the minimum adjacent element and calculate the number of steps i.e. nums[i]-min(nums[i]+1,nums[i- 1]) +1.
• At last, we will return the minimum value of the counts obtained in steps 1 and step 2.

## Code For Decrease Elements To Make Array Zigzag :

### Java Code

```class Solution {
public int movesToMakeZigzag(int[] nums) {

int even = 0, odd = 0, n = nums.length;
//for odd
for(int i=1; i < n; i+= 2){
int min = Math.min(nums[i-1], i+1 < n ? nums[i+1] : 1001);
if(min <= nums[i])
odd += (nums[i]-min+1);
}
// For Even
for(int i=0; i < n; i+= 2){
int min = Math.min(i > 0 ? nums[i-1] : 1001, i+1 < n ? nums[i+1] : 1001);
if(min <= nums[i])
even += (nums[i]-min+1);
}
return Math.min(even,odd);
}

}```

### C++ Code

```class Solution {
public:
int movesToMakeZigzag(vector<int>& nums) {
int even = 0, odd = 0, n = nums.size();
//for odd
for(int i=1; i < n; i+= 2){
int minVal = min(nums[i-1], i+1 < n ? nums[i+1] : 1001);
if(minVal <= nums[i])
odd += (nums[i]-minVal+1);
}
// For Even
for(int i=0; i < n; i+= 2){
int minVal = min(i > 0 ? nums[i-1] : 1001, i+1 < n ? nums[i+1] : 1001);
if(minVal <= nums[i])
even += (nums[i]-minVal+1);
}
return min(even,odd);
}
};```

## Complexity Analysis For Decrease Elements To Make Array Zigzag LeetCode Solution:

### Time Complexity

`O(N)`, N is the length of the array and we are iterating only two times in the array.

### Space Complexity

`O(1)`, as no extra space is used.

Translate »