3785. Minimum Swaps to Avoid Forbidden Values

You are given two integer arrays, nums and forbidden, each of length n.

You may perform the following operation any number of times (including zero):

• Choose two distinct indices i and j, and swap nums[i] with nums[j].

Return the minimum number of swaps required such that, for every index i, the value of nums[i] is not equal to forbidden[i]. If no amount of swaps can ensure that every index avoids its forbidden value, return -1.

class Solution {
public:
    int minSwaps(vector<int>& nums, vector<int>& forbidden) {
        unordered_map<int,int> freq;
        int n = nums.size();
        for(int i = 0; i < n; i++) if(nums[i] == forbidden[i]) freq[nums[i]]++;
        int best = 0, tot = 0;
        for(auto& [k,v] : freq) {
            best = max(best, v);
            tot += v;
        }
        if(best * 2 <= tot) return (tot + 1) / 2;
        int res = tot - best, remain = 2 * best - tot, who = -1;
        for(auto& [k,v] : freq) if(v == best) who = k;
        for(int i = 0; i < n and remain; i++) if(nums[i] != forbidden[i] and forbidden[i] != who and nums[i] != who) {
            remain--;
            res++;
        }
        return remain ? -1 : res;
    }
};