2170. Minimum Operations to Make the Array Alternating

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.

c++

class Solution {
    pair<int,int> getMaxFrequency(unordered_map<int, int>& m) {
        int num = -1, cnt = 0;
        for(auto& [k, count]: m) {
            if(cnt < count) {
                cnt = count;
                num = k;
            }
        }
        return {num, cnt};
    }

    pair<int,int> getSecondMaxFrequency(unordered_map<int, int>& m, int skip) {
        int num = -1, cnt = 0;
        for(auto& [k, count]: m) {
            if(k == skip) continue;
            if(cnt < count) {
                cnt = count;
                num = k;
            }
        }
        return {num, cnt};
    }
public:
    int minimumOperations(vector<int>& nums) {
        if(nums.size() <= 1) return 0;
        if(nums.size() == 2) return nums[0] == nums[1];
        int res = 0, n = nums.size();
        unordered_map<int, int> odd, even;
        for(int i = 0; i < n; i++) {
            if(i&1) odd[nums[i]]++;
            else even[nums[i]]++;
        }
        auto [oddNum, oddMaxFreq] = getMaxFrequency(odd);
        auto [evenNum, evenMaxFreq] = getMaxFrequency(even);
        if(oddNum != evenNum) {
            return n - oddMaxFreq - evenMaxFreq;
        }
        auto [secondOddNum, secondOddFreq] = getSecondMaxFrequency(odd, oddNum);
        auto [secondEvenNum, secondEvenFreq] = getSecondMaxFrequency(even, evenNum);
        return n + min(-oddMaxFreq-secondEvenFreq, -secondOddFreq-evenMaxFreq);
    }
};