Decrease Elements To Make Array Zigzag LeetCode Solution

Difficulty Level Medium
Frequently asked in GoogleViews 1756

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[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 :

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 :

Decrease Elements To Make Array Zigzag LeetCode Solution

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 »