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

Minimum Operations to Make the Array Alternating

Difficulty: Medium

Problem Description

You are given a 0-indexed array nums consisting of n positive integers. The array nums is called alternating if:

  • nums[i - 2] == nums[i], where 2 <= i <= n - 1.
  • nums[i - 1] != nums[i], where 1 <= i <= n - 1.

In one operation, you can choose an index i and change nums[i] into any positive integer. Return the minimum number of operations required to make the array alternating.

Key Insights

  • The array must alternate between two distinct values.
  • The values at even indices must be the same, and the values at odd indices must be the same but different from the even indices.
  • We can count the frequency of elements at even and odd indices separately.
  • The most frequent element at even indices and the most frequent element at odd indices can help minimize operations.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

The solution involves using two frequency maps (or dictionaries) to count the occurrences of elements at even and odd indices. By determining the most frequent elements in both frequency maps, we can calculate the minimum number of changes required to make the array alternating.

  1. Traverse the array, populating two frequency maps: one for even indices and one for odd indices.
  2. Identify the top two most frequent elements in both maps.
  3. Calculate the minimum operations needed based on the chosen elements from the even and odd frequency maps, ensuring they are different.

Code Solutions

from collections import Counter

def min_operations(nums):
    even_count = Counter()
    odd_count = Counter()

    for i in range(len(nums)):
        if i % 2 == 0:
            even_count[nums[i]] += 1
        else:
            odd_count[nums[i]] += 1

    # Get the most common elements and their counts
    even_most_common = even_count.most_common(2)
    odd_most_common = odd_count.most_common(2)

    # Default to (None, 0) if there's no element
    even_first = even_most_common[0] if even_most_common else (None, 0)
    even_second = even_most_common[1] if len(even_most_common) > 1 else (None, 0)

    odd_first = odd_most_common[0] if odd_most_common else (None, 0)
    odd_second = odd_most_common[1] if len(odd_most_common) > 1 else (None, 0)

    # Calculate minimum operations
    total_length = len(nums)
    if even_first[0] != odd_first[0]:  # If the most common are different
        return total_length - even_first[1] - odd_first[1]
    else:  # If they are the same, take the second most common
        return min(total_length - even_first[1] - odd_second[1],
                   total_length - even_second[1] - odd_first[1])

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