Skip to main content

2170 - Minimum Operations to Make the Array Alternating (Medium)

https://leetcode.com/problems/minimum-operations-to-make-the-array-alternating/

Problem Statement

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

Approach 1: Frequency Table

First, we need to separate the numbers at odd positions (odd) and even positions (even).

We are only interested in the top 2 most frequent elements in odd and even. We have the following cases:

  1. The most frequent element from odd and even are different
  2. The most frequent element from odd and even are the same

Case 1 is simple, we just change all other elements from the original list to those 2 elements.

Case 2 is trickier, because we have two possibilities now. As we cannot pick the two top 1 frequent elements from odd and even, we need to inspect the second most frequent element as well. We then have the following two combination:

  1. mostFrequentOdd + secondMostFrequentEven
  2. mostFrequentEven + secondMostFrequentOdd

We pick the larger of the two, and change all other elements to those numbers.

Written by @heiheihang
def minimumOperations(self, nums: List[int]) -> int:
if(len(nums) == 1):
return 0

#create frequency table for odd and even
odd = defaultdict(int)
even = defaultdict(int)

#populate the frequency tables
for i in range(len(nums)):
if(i % 2 == 0):
even[nums[i]] += 1
else:
odd[nums[i]] += 1

#store the [frequency, value] pair to the lists
evens = []
odds = []
for k in odd:
odds.append([odd[k], k])
for k in even:
evens.append([even[k] , k])

#reverse to access the largest elements
odds.sort(reverse = True)
evens.sort(reverse = True)

#case 1: most frequent elements are not equal, then take both
if(odds[0][1] != evens[0][1]):
return len(nums) - odds[0][0] - evens[0][0]
else:

#case 2: find second most frequent element
odd_second = 0
even_second = 0
if(len(odds) > 1):
odd_second = odds[1][0]
if(len(evens) > 1):
even_second = evens[1][0]

#return the larger result
return min(len(nums) - odds[0][0] - even_second, len(nums) - evens[0][0] - odd_second)