Decrease Elements To Make Array Zigzag

Medium
1133.

Decrease Elements To Make Array Zigzag

Decrease Elements To Make Array Zigzag is a medium coding problem on arrays and greedy, asked in Amazon and Google interviews.

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 <= 1000
  • 1 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var movesToMakeZigzag = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

Hints for Decrease Elements To Make Array Zigzag

  1. Hint 1

    Only decreases are allowed. In each pattern, which elements would you ever want to decrease — the peaks or the valleys?

  2. Hint 2

    Lowering a peak only makes things worse for its neighbouring valleys, so in a fixed pattern only the valleys move.

  3. 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

  1. For each index i, let low be the minimum of its existing neighbours.
  2. If nums[i] >= low, making i a valley costs nums[i] - low + 1; otherwise it costs 0.
  3. Add that cost to the total for parity i % 2.
  4. 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