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.
-
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]); } }