LeetCode Solutions Blog

Minimum Operations to Make the Array Alternating

Number: 2289

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of positive integers, you must convert it into an alternating array. An alternating array satisfies two rules:

For any index i (i ≥ 2), nums[i] == nums[i-2].
For any index i (i ≥ 1), nums[i] != nums[i-1].

In one operation, you can change any element to any positive integer. Determine the minimum number of operations required to achieve an alternating array.

Key Insights

Split the array into two groups: elements at even indices and elements at odd indices.
For each group, count the frequency of the numbers.
To minimize operations, ideally choose the most frequent number from the even group and the most frequent number from the odd group.
If the most frequent numbers in both groups are the same, choose the next most frequent option in one of the groups to avoid conflict.
Calculate operations as the total changes needed in each group.

Space and Time Complexity

Time Complexity: O(n) — We traverse the list and count frequencies. Space Complexity: O(n) — Storing counts for numbers in two groups.

Solution

We first compute frequency counts separately for even indices and odd indices. Then, we extract the top two frequent numbers along with their frequencies for both groups. If the top choices for even and odd groups are different, the answer is the sum of (number of even indices minus top frequency for even) and (number of odd indices minus top frequency for odd). If they are the same, we try substituting one group’s top choice with its second most frequent and take the minimal result among the two replacement options.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def minimumOperations(self, nums: list[int]) -> int:
        from collections import Counter
        
        # Count frequencies for even and odd indexed numbers
        even_freq = Counter(nums[i] for i in range(0, len(nums), 2))
        odd_freq = Counter(nums[i] for i in range(1, len(nums), 2))
        
        # Function to get the two most common items with frequency.
        def get_top_two(freq):
            # Get the most common elements in descending order of frequency
            common = freq.most_common(2)
            # Append a dummy if less than two elements exist
            if len(common) == 1:
                common.append((None, 0))
            return common
        
        (even_val1, even_count1), (even_val2, even_count2) = get_top_two(even_freq)
        (odd_val1, odd_count1), (odd_val2, odd_count2) = get_top_two(odd_freq)
        
        n_even = (len(nums) + 1) // 2  # number of even indexed elements
        n_odd = len(nums) // 2         # number of odd indexed elements
        
        # If the top values for even and odd indices differ, no conflict.
        if even_val1 != odd_val1:
            return (n_even - even_count1) + (n_odd - odd_count1)
        
        # If they are the same, consider both replacement options (substitute one group top with its second most)
        option1 = (n_even - even_count1) + (n_odd - odd_count2)
        option2 = (n_even - even_count2) + (n_odd - odd_count1)
        return min(option1, option2)