Scale Engineer

Decrease Elements To Make Array Zigzag

Med
#1077Time: O(N), where N is the length of the input array. We perform two separate passes, one for each pattern, and each pass iterates through roughly N/2 elements.Space: O(N), where N is the length of the input array. We create two copies of the array, each of size N.
Patterns
Greedy
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach calculates the minimum moves for the two possible zigzag patterns separately. For each pattern, it works on a copy of the input array to calculate the total moves required. The final answer is the minimum of the costs for the two patterns. This method is straightforward but uses extra memory.

Algorithm

  • Create two copies of the input array, nums1 and nums2.
  • Calculate moves for the first zigzag pattern (< > < ...):
    • Initialize moves1 = 0.
    • Iterate through nums1 at even indices (i = 0, 2, 4, ...).
    • For each nums1[i], find the minimum of its neighbors. Use a very large number if a neighbor is out of bounds.
    • If nums1[i] is not smaller than its minimum neighbor, calculate the necessary moves (nums1[i] - minNeighbor + 1) and add to moves1.
  • Calculate moves for the second zigzag pattern (> < > ...):
    • Initialize moves2 = 0.
    • Iterate through nums2 at odd indices (i = 1, 3, 5, ...).
    • For each nums2[i], find the minimum of its neighbors.
    • If nums2[i] is not smaller than its minimum neighbor, calculate the necessary moves and add to moves2.
  • Return the minimum of moves1 and moves2.

Walkthrough

The problem asks for the minimum moves to make an array zigzag. A zigzag array can follow one of two patterns:

  1. A[0] < A[1] > A[2] < A[3] > ... (odd-indexed elements are peaks)
  2. A[0] > A[1] < A[2] > A[3] < ... (even-indexed elements are peaks)

Since we can only decrease elements, to make an element A[i] a 'peak', we must decrease its neighbors. To make A[i] a 'valley', we must decrease A[i] itself. This implies that for each pattern, the elements being modified are independent. For pattern 1, we only modify even-indexed elements. For pattern 2, we only modify odd-indexed elements.

This approach computes the cost for each pattern independently and then compares them. To ensure the calculations for one pattern do not interfere with the other, we use copies of the original array.

For Pattern 1 (< > < ...): We iterate through the even-indexed elements (nums[0], nums[2], ...) on a copy of the array. For each such element nums[i], it must be smaller than its neighbors. If nums[i] is greater than or equal to min(left_neighbor, right_neighbor), we must decrease it. The number of moves is nums[i] - (min(left_neighbor, right_neighbor) - 1). We sum these moves.

For Pattern 2 (> < > ...): Similarly, we iterate through the odd-indexed elements (nums[1], nums[3], ...) on a second copy. For each nums[i], we calculate the moves needed to make it smaller than its neighbors and sum them up.

Finally, we return the minimum of the two calculated costs.

import java.util.Arrays; class Solution {    public int movesToMakeZigzag(int[] nums) {        // Case 1: Make odd-indexed elements peaks (< > < ...)        // This means we might need to decrease even-indexed elements.        int[] nums1 = Arrays.copyOf(nums, nums.length);        int moves1 = 0;        for (int i = 0; i < nums1.length; i += 2) {            int left = (i > 0) ? nums1[i - 1] : Integer.MAX_VALUE;            int right = (i < nums1.length - 1) ? nums1[i + 1] : Integer.MAX_VALUE;            int minNeighbor = Math.min(left, right);            if (nums1[i] >= minNeighbor) {                moves1 += nums1[i] - minNeighbor + 1;            }        }         // Case 2: Make even-indexed elements peaks (> < > ...)        // This means we might need to decrease odd-indexed elements.        int[] nums2 = Arrays.copyOf(nums, nums.length);        int moves2 = 0;        for (int i = 1; i < nums2.length; i += 2) {            int left = (i > 0) ? nums2[i - 1] : Integer.MAX_VALUE;            int right = (i < nums2.length - 1) ? nums2[i + 1] : Integer.MAX_VALUE;            int minNeighbor = Math.min(left, right);            if (nums2[i] >= minNeighbor) {                moves2 += nums2[i] - minNeighbor + 1;            }        }         return Math.min(moves1, moves2);    }}

Complexity

Time

O(N), where N is the length of the input array. We perform two separate passes, one for each pattern, and each pass iterates through roughly N/2 elements.

Space

O(N), where N is the length of the input array. We create two copies of the array, each of size N.

Trade-offs

Pros

  • The logic is clear as it completely separates the computation for the two patterns.

  • Guaranteed to be correct as it explores both required outcomes.

Cons

  • Uses O(N) extra space to store copies of the array, which is unnecessary.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem