2170

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

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

Similar Questions:

• Minimum Number of Flips to Make the Binary String Alternating (Medium)

Solution 1. Counting

// OJ: https://leetcode.com/problems/minimum-operations-to-make-the-array-alternating/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int minimumOperations(vector<int>& A) {
        unordered_map<int, int> odd, even;
        for (int i = 0; i < A.size(); ++i) {
            if (i % 2) odd[A[i]]++;
            else even[A[i]]++;
        }
        int oddCnt[2] = {}, oddNum[2] = {}, evenCnt[2] = {}, evenNum[2] = {};
        for (auto &[n, cnt] : odd) {
            if (cnt > oddCnt[0]) oddCnt[1] = oddCnt[0], oddNum[1] = oddNum[0], oddCnt[0] = cnt, oddNum[0] = n;
            else if (cnt > oddCnt[1]) oddCnt[1] = cnt, oddNum[1] = n;
        }
        for (auto &[n, cnt] : even) {
            if (cnt > evenCnt[0]) evenCnt[1] = evenCnt[0], evenNum[1] = evenNum[0], evenCnt[0] = cnt, evenNum[0] = n;
            else if (cnt > evenNum[1]) evenCnt[1] = cnt, evenNum[1] = n;
        }
        if (oddNum[0] != evenNum[0]) return A.size() - oddCnt[0] - evenCnt[0];
        return min(A.size() - oddCnt[0] - evenCnt[1], A.size() - evenCnt[0] - oddCnt[1]);
    }
};