LeetCode 2170 - Minimum Operations to Make the Array Alternating

The problem requires transforming a given integer array nums into an alternating array with the minimum number of operations.

leetcodemediumarrayhash-tablegreedycounting

LeetCode Problem 2170

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy, Counting

Solution

Problem Understanding

The problem requires transforming a given integer array nums into an alternating array with the minimum number of operations. An array is alternating if elements at even indices repeat every two steps (nums[i] == nums[i-2] for i >= 2) and elements at odd indices differ from their previous element (nums[i] != nums[i-1]). In practical terms, this means that all even-indexed positions should ideally contain one repeated number, all odd-indexed positions another number, and the two numbers should differ.

The input is a list of positive integers, and the output is a single integer representing the minimum number of changes needed to satisfy the alternating property. Constraints indicate that the array can be very large (n up to 100,000) and the values can also be large (nums[i] up to 100,000), so any solution must scale efficiently in both time and space.

Important edge cases include arrays with length 1 (already alternating by default), arrays where all elements are identical, arrays with two distinct repeating numbers, and arrays where multiple numbers compete for the majority at even and odd positions. A naive approach of trying every combination would be far too slow.

Approaches

The brute-force approach would involve attempting to try every possible pair of numbers for even and odd positions, counting the number of changes required for each pair, and taking the minimum. While correct, this approach has a time complexity of $O(k^2 n)$, where $k$ is the number of unique values in nums. For the worst case, where all numbers are unique, this approach is far too slow.

The optimal approach leverages a key observation: the best choice for even and odd positions is typically the most frequent numbers at those positions. By counting frequencies separately for even and odd indices, we can focus on the top one or two most common numbers for each. If the most frequent numbers at even and odd positions differ, we can directly use them. If they are the same, we choose the combination that minimizes the total operations using the second-most frequent number at one of the positions. This approach is greedy and works because maximizing the number of positions that already have the desired value minimizes changes.

Approach Time Complexity Space Complexity Notes
Brute Force O(k² n) O(k) Try all pairs of numbers for even and odd positions
Optimal O(n) O(k) Count frequencies at even and odd positions and choose top 1-2 candidates

Algorithm Walkthrough

  1. Initialize two dictionaries, even_count and odd_count, to store frequency counts of numbers at even and odd indices respectively.
  2. Iterate through the array. For each element at index i, increment the count in even_count if i is even, or in odd_count if i is odd.
  3. Extract the top two most frequent numbers for even indices and odd indices. If there is only one unique number, the second frequency can be considered 0 with a placeholder number.
  4. If the most frequent numbers for even and odd positions differ, the minimum operations is the number of elements minus the sum of these top frequencies.
  5. If the most frequent numbers are the same, consider two options: use the top number for even and second for odd, or top for odd and second for even. The answer is the option that minimizes total operations.
  6. Return the minimum number of operations calculated.

Why it works: By maximizing the number of positions that already contain the chosen numbers for even and odd indices, we minimize the total number of changes required. This greedy choice is valid because no other number selection can reduce the number of operations further.

Python Solution

from collections import Counter
from typing import List

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        
        even_count = Counter(nums[i] for i in range(0, len(nums), 2))
        odd_count = Counter(nums[i] for i in range(1, len(nums), 2))
        
        # Get the most common numbers and their counts
        even_common = even_count.most_common(2)
        odd_common = odd_count.most_common(2)
        
        even1, even1_count = even_common[0] if even_common else (0, 0)
        even2, even2_count = even_common[1] if len(even_common) > 1 else (0, 0)
        odd1, odd1_count = odd_common[0] if odd_common else (0, 0)
        odd2, odd2_count = odd_common[1] if len(odd_common) > 1 else (0, 0)
        
        if even1 != odd1:
            return len(nums) - (even1_count + odd1_count)
        else:
            option1 = len(nums) - (even1_count + odd2_count)
            option2 = len(nums) - (even2_count + odd1_count)
            return min(option1, option2)

The implementation counts the frequency of numbers separately at even and odd positions, identifies the top candidates, and then determines the minimal operations. Special handling ensures that if the top candidates clash, we evaluate the next-best frequencies to find the minimum number of changes.

Go Solution

package main

func minimumOperations(nums []int) int {
    n := len(nums)
    if n == 1 {
        return 0
    }

    evenCount := map[int]int{}
    oddCount := map[int]int{}

    for i, num := range nums {
        if i%2 == 0 {
            evenCount[num]++
        } else {
            oddCount[num]++
        }
    }

    type pair struct {
        val, cnt int
    }
    getTopTwo := func(countMap map[int]int) [2]pair {
        top := [2]pair{{0, 0}, {0, 0}}
        for num, cnt := range countMap {
            if cnt > top[0].cnt {
                top[1] = top[0]
                top[0] = pair{num, cnt}
            } else if cnt > top[1].cnt {
                top[1] = pair{num, cnt}
            }
        }
        return top
    }

    evenTop := getTopTwo(evenCount)
    oddTop := getTopTwo(oddCount)

    if evenTop[0].val != oddTop[0].val {
        return n - (evenTop[0].cnt + oddTop[0].cnt)
    }

    option1 := n - (evenTop[0].cnt + oddTop[1].cnt)
    option2 := n - (evenTop[1].cnt + oddTop[0].cnt)
    return min(option1, option2)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

The Go version follows the same logic but uses maps instead of Counter, and manually extracts the top two elements for both even and odd positions. It also handles the edge case of a single-element array.

Worked Examples

Example 1: nums = [3,1,3,2,4,3]

  • Even indices: [3,3,4] → most common: 3 (2 times), second: 4 (1 time)
  • Odd indices: [1,2,3] → most common: 1, 2, or 3? 1 (1), 2 (1), 3 (1) → pick 1, second: 2

Since top even and odd numbers differ (3 != 1), minimum operations = 6 - (2 + 1) = 3.

Example 2: nums = [1,2,2,2,2]

  • Even indices: [1,2,2] → 2 appears 2 times, 1 appears 1 time
  • Odd indices: [2,2] → 2 appears 2 times, second most 0

Top even and odd numbers are both 2 → conflict.

Option1: even top (2) + odd second (0) → 5 - (2 + 0) = 3

Option2: even second (1) + odd top (2) → 5 - (1 + 2) = 2 → minimum = 2

Complexity Analysis

Measure Complexity Explanation
Time O(n) Count frequencies in one pass and find top two in O(k) where k ≤ n
Space O(k) Store frequency counts for even and odd indices

Counting and comparison operations are efficient because the number of unique elements k is bounded by n.

Test Cases

# Provided examples
assert Solution().minimumOperations([3,1,3,2,4,3]) == 3  # alternating possible
assert Solution().minimumOperations([1,2,2,2,2]) == 2  # conflict resolution

# Edge cases
assert Solution().minimumOperations([1]) == 0  # single element
assert Solution().minimumOperations([1,1]) == 1  # two identical elements
assert Solution().minimumOperations([1,2]) == 0  # already alternating
assert Solution().minimumOperations([1,1,1,1,1,1]) == 3  # all identical
assert Solution().