Decrease Elements To Make Array Zigzag - Leetcode Solution

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.

Solution:

We can solve this problem by iterating over the array and comparing elements at even and odd indices. For the even indices, we need to ensure that the current element is greater than its adjacent elements. Similarly, for the odd indices, the current element should be smaller than its adjacent elements.

To make the current element compliant with the zigzag property, we need to calculate the required decrease in the element. Let's say the element at position i is nums[i]. Then, for an even index i, we need to ensure the following property: nums[i] > min(nums[i-1], nums[i+1]). Similarly, for an odd index i, the following property must hold true: nums[i] < max(nums[i-1], nums[i+1]).

Once we have the required decrease in the element, we will calculate the sum of all decreases and return it as the output.

Here is the detailed algorithm for this problem:

1. Initialize variable total_decrease to 0.
2. Iterate over the elements of the array from second index to second-last index.
3. If the index i is even, check if nums[i] is not greater than its adjacent elements.
4. If not, calculate the decrease required and add it to total_decrease.
5. If the index i is odd, check if nums[i] is not smaller than its adjacent elements.
6. If not, calculate the decrease required and add it to total_decrease.
7. Return total_decrease.

Here is the Python code that implements the above algorithm:

class Solution:
    def movesToMakeZigzag(self, nums: List[int]) -> int:
        total_decrease = 0
        for i in range(1, len(nums)-1):
            if i % 2 == 0:
                if nums[i] >= nums[i-1]:
                    decrease = nums[i] - nums[i-1] + 1
                    total_decrease += decrease
                    nums[i] -= decrease
                if nums[i] >= nums[i+1]:
                    decrease = nums[i] - nums[i+1] + 1
                    total_decrease += decrease
                    nums[i] -= decrease
            else:
                if nums[i] <= nums[i-1]:
                    decrease = nums[i-1] - nums[i] + 1
                    total_decrease += decrease
                    nums[i] += decrease
                if nums[i] <= nums[i+1]:
                    decrease = nums[i+1] - nums[i] + 1
                    total_decrease += decrease
                    nums[i] += decrease
        return total_decrease

Time Complexity: O(n) Space Complexity: O(1)

Code Explanation:

We initialize total_decrease to 0 and iterate over the elements of the array from the second index to the second-last index. For every even index i, we check if nums[i] is not greater than its adjacent elements. If so, we calculate the required decrease, add it to total_decrease, and subtract it from nums[i]. Similarly, for every odd index i, we check if nums[i] is not smaller than its adjacent elements, and if so, we calculate the required decrease, add it to total_decrease, and add it to nums[i].

After iterating over all the elements, we return total_decrease as the output.

1