Formatted question description: https://leetcode.ca/all/1144.html

1144. Decrease Elements To Make Array Zigzag

Level

Medium

Description

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 <= 1000
  • 1 <= nums[i] <= 1000

Solution

To transform the given array nums into a zigzag array, either decrease the elements at even indices or decrease the elements at odd indices.

For each index where the element needs to be decreased, decrease the element at the index until it is less than its one adjacent element if it is at the start or the end of the array, or it is less than both its adjacent elements in other cases. If the element is initially less than its adjacent elements, then do not decrease it.

Return the minimum number of moves of decreasing elements at even indices and decreasing elements at odd indices.

class Solution {
    public int movesToMakeZigzag(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int length = nums.length;
        if (length == 1)
            return 0;
        if (length == 2)
            return nums[0] == nums[1] ? 1 : 0;
        int evenCounts = 0, oddCounts = 0;
        for (int i = 0; i < length; i += 2) {
            int num = nums[i];
            int minAdjacent = 0;
            if (i == 0)
                minAdjacent = nums[1];
            else if (i == length - 1)
                minAdjacent = nums[length - 2];
            else
                minAdjacent = Math.min(nums[i - 1], nums[i + 1]);
            evenCounts += Math.max(0, num - minAdjacent + 1);
        }
        for (int i = 1; i < length; i += 2) {
            int num = nums[i];
            int minAdjacent = 0;
            if (i == length - 1)
                minAdjacent = nums[length - 2];
            else
                minAdjacent = Math.min(nums[i - 1], nums[i + 1]);
            oddCounts += Math.max(0, num - minAdjacent + 1);
        }
        return Math.min(evenCounts, oddCounts);
    }
}

All Problems

All Solutions