Decrease Elements To Make Array Zigzag — Problem & Solution
Decrease Elements To Make Array Zigzag solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Decrease Elements To Make Array Zigzag is a medium coding problem on arrays and greedy, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
In one move you may choose any element of nums and decrease it by 1 (values may drop to zero or below).
An array is a zigzag array if one of these holds:
- every even-indexed element is greater than its neighbours:
A[0] > A[1] < A[2] > A[3] < ..., or - every odd-indexed element is greater than its neighbours:
A[0] < A[1] > A[2] < A[3] > ....
Return the minimum number of moves needed to turn nums into a zigzag array.
Example 1
Input: nums = [4,4,4]
Output: 1
Explanation: Lower the middle 4 to 3.
Example 2
Input: nums = [5,1,5,1,5]
Output: 0
Explanation: Already a zigzag.
Example 3
Input: nums = [6,5,6,7,7]
Output: 2
Explanation: Lower index 3 from 7 to 5, giving `[6,5,6,5,7]`.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 1000
Hints for Decrease Elements To Make Array Zigzag
Hint 1
Only decreases are allowed. In each pattern, which elements would you ever want to decrease — the peaks or the valleys?
Hint 2
Lowering a peak only makes things worse for its neighbouring valleys, so in a fixed pattern only the valleys move.
Hint 3
For each of the two patterns, push every valley down to one less than its smaller neighbour (if it is not already below both), sum the cost, and take the cheaper pattern.
How to solve Decrease Elements To Make Array Zigzag
Fix which parity holds the valleys; then the peaks never need to change, and each valley independently drops to just below its smaller neighbour.
Approach
- For each index
i, letlowbe the minimum of its existing neighbours. - If
nums[i] >= low, makingia valley costsnums[i] - low + 1; otherwise it costs 0. - Add that cost to the total for parity
i % 2. - Return the smaller of the two totals.
Why it works
In a chosen pattern, decreasing a peak can only raise the cost of the valleys beside it, so an optimal solution leaves every peak at its original value. Valleys are never adjacent to each other, so each valley's cost depends only on the original values of its neighbours, and the cheapest choice is to stop exactly one below the smaller of them.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Using already-decreased neighbour values is wrong — a valley's neighbours are peaks, which never change.
- End elements have only one neighbour; a single-element array is trivially zigzag.
- The valley must be strictly smaller, hence the
+ 1.
Reference solution
Python
from typing import List
def movesToMakeZigzag(nums: List[int]) -> int:
n = len(nums)
cost = [0, 0]
for i in range(n):
low = float("inf")
if i > 0:
low = min(low, nums[i - 1])
if i + 1 < n:
low = min(low, nums[i + 1])
if nums[i] >= low:
cost[i % 2] += nums[i] - low + 1
return int(min(cost))Java
public static int movesToMakeZigzag(int[] nums) {
int n = nums.length;
int[] cost = new int[2];
for (int i = 0; i < n; i++) {
int low = Integer.MAX_VALUE;
if (i > 0) low = Math.min(low, nums[i - 1]);
if (i + 1 < n) low = Math.min(low, nums[i + 1]);
if (nums[i] >= low) cost[i % 2] += nums[i] - low + 1;
}
return Math.min(cost[0], cost[1]);
}C++
int movesToMakeZigzag(vector<int>& nums) {
int n = nums.size();
int cost[2] = { 0, 0 };
for (int i = 0; i < n; i++) {
int low = INT_MAX;
if (i > 0) low = min(low, nums[i - 1]);
if (i + 1 < n) low = min(low, nums[i + 1]);
if (nums[i] >= low) cost[i % 2] += nums[i] - low + 1;
}
return min(cost[0], cost[1]);
}JavaScript
var movesToMakeZigzag = function(nums) {
var n = nums.length;
var cost = [0, 0];
for (var i = 0; i < n; i++) {
var low = 2147483647;
if (i > 0) low = Math.min(low, nums[i - 1]);
if (i + 1 < n) low = Math.min(low, nums[i + 1]);
if (nums[i] >= low) cost[i % 2] += nums[i] - low + 1;
}
return Math.min(cost[0], cost[1]);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms