Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• C#

• 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);
      }
  }
  

• // OJ: https://leetcode.com/problems/decrease-elements-to-make-array-zigzag/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int movesToMakeZigzag(vector<int>& A) {
          int sum[2] = {}, N = A.size();
          for (int i = 0; i < N; ++i) sum[i % 2] += max(0, A[i] - min(i == 0 ? INT_MAX : A[i - 1], i == N - 1 ? INT_MAX : A[i + 1]) + 1);
          return min(sum[0], sum[1]);
      }
  };
  

• class Solution:
      def movesToMakeZigzag(self, nums: List[int]) -> int:
          ans = [0, 0]
          n = len(nums)
          for i in range(2):
              for j in range(i, n, 2):
                  d = 0
                  if j:
                      d = max(d, nums[j] - nums[j - 1] + 1)
                  if j < n - 1:
                      d = max(d, nums[j] - nums[j + 1] + 1)
                  ans[i] += d
          return min(ans)
  
  ############
  
  # 1144. Decrease Elements To Make Array Zigzag
  # https://leetcode.com/problems/decrease-elements-to-make-array-zigzag/
  
  class Solution:
      def movesToMakeZigzag(self, A: List[int]) -> int:
          n = len(A)
          
          def helper(start):
              nums = A[:]
              count = 0
              
              for i in range(start, n, 2):
                  if i - 1 >= 0 and nums[i] <= nums[i - 1]:
                      move = max(0, nums[i] - 1)
                      
                      if nums[i] > move:
                          count += abs(move - nums[i - 1])
                          nums[i - 1] = move
                      else:
                          return float('inf')
                  
                  if i + 1 < n and nums[i] <= nums[i + 1]:
                      move = max(0, nums[i] - 1)
                          
                      if nums[i] > move:
                          count += abs(move - nums[i + 1])
                          nums[i + 1] = move
                      else:
                          return float('inf')
  
              
              return count
          
          return min(helper(0), helper(1))
                  
  
  

• func movesToMakeZigzag(nums []int) int {
  	ans := [2]int{}
  	n := len(nums)
  	for i := 0; i < 2; i++ {
  		for j := i; j < n; j += 2 {
  			d := 0
  			if j > 0 {
  				d = max(d, nums[j]-nums[j-1]+1)
  			}
  			if j < n-1 {
  				d = max(d, nums[j]-nums[j+1]+1)
  			}
  			ans[i] += d
  		}
  	}
  	return min(ans[0], ans[1])
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  
  func min(a, b int) int {
  	if a < b {
  		return a
  	}
  	return b
  }
  

• public class Solution {
      public int MovesToMakeZigzag(int[] nums) {
          int[] ans = new int[2];
          int n = nums.Length;
          for (int i = 0; i < 2; ++i) {
              for (int j = i; j < n; j += 2) {
                  int d = 0;
                  if (j > 0) {
                      d = Math.Max(d, nums[j] - nums[j - 1] + 1);
                  }
                  if (j < n - 1) {
                      d = Math.Max(d, nums[j] - nums[j + 1] + 1);
                  }
                  ans[i] += d;
              }
          }
          return Math.Min(ans[0], ans[1]);
      }
  }
  

All Problems

All Solutions