We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Decrease Elements To Make Array Zigzag

Number: 1247

Difficulty: Medium

Paid? No

Companies: Adobe, Google

Problem Description

Given an integer array nums, you can perform a move by selecting any element and decreasing it by 1. The goal is to transform the array into a zigzag array. An array is zigzag if either every even-indexed element is greater than its adjacent elements (i.e., A[0] > A[1] < A[2] > A[3] < ...) or every odd-indexed element is greater than its adjacent elements (i.e., A[0] < A[1] > A[2] < A[3] > ...). Return the minimum number of moves required to convert nums into a zigzag array.

Key Insights

  • Only decreasing operations are allowed; you cannot increase an element.
  • There are two possible target patterns: even-indexed peaks (and odd-indexed valleys) or odd-indexed peaks (and even-indexed valleys).
  • For a valley element, to satisfy the zigzag condition it must be strictly less than both neighbors.
  • For each valley index, if the current value is not less than the minimum of its neighbors, decrease it to be one less than that minimum.
  • Compute the number of moves required for both patterns and return the minimum.

Space and Time Complexity

Time Complexity: O(n) – We traverse the array a constant number of times. Space Complexity: O(1) – Only a few extra variables are used.

Solution

We solve this problem by considering the two valid zigzag patterns separately. For each pattern, we identify the indices that should be valleys. For each valley index, we compare the current value with its left and right neighbors (treating missing neighbors as infinity) and calculate the number of moves needed to make the valley element strictly less than its smallest neighbor (i.e., reduce it to min(neighbor) - 1). Finally, we return the minimum total moves between the two patterns. This greedy approach efficiently computes the answer in one pass per pattern.

Code Solutions

def movesToMakeZigzag(nums):
    n = len(nums)
    # Helper function to calculate moves required for indices in valley_indices
    def calculate_moves(valley_indices):
        moves = 0
        for i in range(n):
            if i in valley_indices:
                # If no left neighbor, treat as infinity.
                left = nums[i - 1] if i - 1 >= 0 else float('inf')
                # If no right neighbor, treat as infinity.
                right = nums[i + 1] if i + 1 < n else float('inf')
                min_neighbor = min(left, right)
                if nums[i] >= min_neighbor:
                    # Decrease current element to (min_neighbor - 1)
                    moves += nums[i] - min_neighbor + 1
        return moves

    # Case 1: Even indices as peaks, so odd indices are valleys.
    valley_indices_case1 = set(range(1, n, 2))
    moves_case1 = calculate_moves(valley_indices_case1)
    # Case 2: Odd indices as peaks, so even indices are valleys.
    valley_indices_case2 = set(range(0, n, 2))
    moves_case2 = calculate_moves(valley_indices_case2)
    return min(moves_case1, moves_case2)

# Example usage:
print(movesToMakeZigzag([1, 2, 3]))      # Output: 2
print(movesToMakeZigzag([9, 6, 1, 6, 2]))  # Output: 4
← Back to All Questions