2170. Minimum Operations to Make the Array Alternating #

Problem #

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.

Example 1:

Input: nums = [3,1,3,2,4,3]
Output: 3
Explanation:
One way to make the array alternating is by converting it to [3,1,3,1,3,1].
The number of operations required in this case is 3.
It can be proven that it is not possible to make the array alternating in less than 3 operations.

Example 2:

Input: nums = [1,2,2,2,2]
Output: 2
Explanation:
One way to make the array alternating is by converting it to [1,2,1,2,1].
The number of operations required in this case is 2.
Note that the array cannot be converted to [2,2,2,2,2] because in this case nums[0] == nums[1] which violates the conditions of an alternating array.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Problem Summary #

You are given a 0-indexed array nums, which consists of n positive integers.

If the following conditions are satisfied, then the array nums is an alternating array:

• 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] to any positive integer. Return the minimum number of operations required to make the array alternating.

Note:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

Solution Approach #

• The problem asks for the minimum number of operations, which means keeping the number with the highest frequency and replacing all remaining numbers with this number. First count the frequency of each number, then sort by frequency in descending order. Prioritize choosing numbers with higher frequencies.
• There are several “special” cases to handle: when the most frequent number at odd indices and the most frequent number at even indices are the same (same number, different frequencies), the number with the higher frequency should be kept; when the number is the same and the frequency is also the same, we need to look at how many distinct numbers there are at odd indices and even indices respectively. If one of them has only one distinct number, then all numbers in the other group need to be changed to the number with the second-highest frequency in that group. For example, the numbers at odd indices are all 1, with frequency 3, and among the numbers at even indices, 1 has the highest frequency of 2. The number with the second-highest frequency is 9, with frequency 1. In this case, choose 1 for the odd-indexed numbers and 9 for the even-indexed numbers. Change the even-indexed numbers that are not 9 into 9; furthermore, if both odd indices and even indices have only one distinct number and the frequencies are the same, then all numbers at either odd indices or even indices must be changed.

Code #

package leetcode

import (
	"sort"
)

type node struct {
	value int
	count int
}

func minimumOperations(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	res, odd, even, oddMap, evenMap := 0, []node{}, []node{}, map[int]int{}, map[int]int{}

	for i := 0; i < len(nums); i += 2 {
		evenMap[nums[i]]++
	}
	for k, v := range evenMap {
		even = append(even, node{value: k, count: v})
	}
	sort.Slice(even, func(i, j int) bool {
		return even[i].count > even[j].count
	})

	for i := 1; i < len(nums); i += 2 {
		oddMap[nums[i]]++
	}
	for k, v := range oddMap {
		odd = append(odd, node{value: k, count: v})
	}
	sort.Slice(odd, func(i, j int) bool {
		return odd[i].count > odd[j].count
	})

	if even[0].value == odd[0].value {
		if len(even) == 1 && len(odd) != 1 {
			res = len(nums) - even[0].count - odd[1].count
		} else if len(odd) == 1 && len(even) != 1 {
			res = len(nums) - odd[0].count - even[1].count
		} else if len(odd) == 1 && len(even) == 1 {
			res = len(nums) / 2
		} else {
			// both != 1
			res = min(len(nums)-odd[0].count-even[1].count, len(nums)-odd[1].count-even[0].count)
		}
	} else {
		res = len(nums) - even[0].count - odd[0].count
	}
	return res
}

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