Skip to content

2170. Minimum Operations to Make the Array Alternating

Difficulty Topics

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.

 

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 <= 105
  • 1 <= nums[i] <= 105

Solution

minimum-operations-to-make-the-array-alternating.py
class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1: return 0

        odd, even = Counter(), Counter()

        for i, x in enumerate(nums):
            if i % 2 == 0:
                even[x] += 1
            else:
                odd[x] += 1

        o = sorted(odd.items(), key = lambda x : -x[1])
        e = sorted(even.items(), key = lambda x : -x[1])

        if o[0][0] == e[0][0]:
            res = max(o[0][1], e[0][1])

            if len(e) > 1:
                res = max(res, o[0][1] + e[1][1])

            if len(o) > 1:
                res = max(res, o[1][1] + e[0][1])

            return n - res
        else:
            return n - o[0][1] - e[0][1]