LC 2561: Intuition.

Find the problem description here. If you would like to read the solution in leetcode platform, find it here.

---

Intuition

Same as the other's solution but, I will explain my own intuition here and how I approached the problem.

By looking at the problem, immediately, you can realize that if you flatten the two baskets, i.e., lay flat all of the numbers from both the given arrays in a sorted order, if you end up getting the frequency of every number "even" then the baskets are valid or else the answer is -1.

The final basket arrangement is something you will get when you lay flat all the numbers from both the baskets in sorted order and sequentially assign each number - one for the basket 1 and one for the basket 2.

But, that isn't all of it. We want the minimum cost of swaps such that, the basket arrangement will end up being something that is explained above.

Now, cost = min(a, b) if a and b are swapped. How do we decide which numbers to swap? It is very simple. If the number a is present 4 times in the basket 1 and only 2 times in the basket 2, then you have to put that one a from the basket 1 into the basket 2. But, here you need to SWAP. Hence, you need something from the basket 2 with the same requirements. Let us say, b is a number that is present 3 times in the basket 2 and only 1 time in the basket 1.

So, we can swap a and b right? right????? say, YES MASTER. Nope! *Spank*.

The cost of the above swap will be min(a, b). But what if, there is an element which is smaller than min(a, b) / 2 and we can do two swaps using it like say $x < min(a, b) / 2$ and we do swap(x, a) and then again swap(x, b). We don't change the basket in which x is present, but we ultimately swapped a and b. The cost is min(x, a) + min(x, b) which will be lesser than min(a, b). How cool is that!!

Now, which element has the potential of being this helper swap thingy here? The minimum of all elements ofcourse. But, we need to make sure it is lesser than the half of the minimum of two elements which we want to swap such that when we do two swaps and add the minimum element two times, it should end up having lesser cost than taking the mninimum of the two elements which we are trying to swap.

Onwards, the approach becomes pretty straight-forward. We take all the swaps that we want, you know the ones which are present irregularly in the given baskets. Of course, we have to check for the ones which are having odd frequency, those are bad boys, we need to return -1 even if there is single bad boy as such. We don't love bad boys, we love good boys.

Among the swaps, if say we have m swaps required, we need to consider only the first minimum m/2 elements because those are the ones that will add up to the cost. And for every one of those, we need to first make sure that we can't use the minimum element present to our advantage. If we can use minimum element, we have to add it twice to the cost or else add the current element to the cost.

That's it folks.

---

Complexity

• Time complexity: $O(n*logn)$

---

Code

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        int n = basket1.size();
        // freq
        unordered_map<int, long long> mp1, mp2;
        for (int i = 0; i < n; ++i) {
            mp1[basket1[i]]++;
            mp2[basket2[i]]++;
        }

        // the elements that are required to be swapped
        // with the number of them required to be swapped
        // you can also consider using an array here. you know personal preference. but, map will handle all the duplicates at once.
        map<int, long long> swaps;
        long long swapsRem = 0; // total elements involved in the swaps

        // elements that are in basket 1
        // and that are may or may not present in basket 2
        for (auto it : mp1) {
            long long freqA = it.second;
            long long freqB = 0;
            if (mp2.count(it.first))    freqB += mp2[it.first];

            // if the total frequency is even, then only possible to split
            // or else, it is not possible have it equally on either side
            if ((freqA + freqB) % 2 == 0) {
                if (freqA == freqB) continue;
                else {
                    swaps[it.first] = abs(freqA - freqB) / 2;
                    swapsRem += abs(freqA - freqB) / 2;
                }
            } else {
                return -1;
            }
        }

        // elements that are only present in basket 2
        for (auto it : mp2) {
            long long freqA = it.second;
            if (mp1.count(it.first))    continue;

            if (freqA % 2 == 0) {
                swaps[it.first] = freqA / 2;
                swapsRem += freqA / 2;
            } else {
                return -1;
            }
        }

        int minEle = *min_element(basket1.begin(), basket1.end());
        minEle = min(minEle, *min_element(basket2.begin(), basket2.end()));
        
        /*
        number of swaps required is the half of the elements to be swapped
        so, if there are 6 elements that need to be swapped
        you will choose the first 3 minimum elements, and then
        swap the first minimum with the first max, second min with second max
        and so on.
        */
        swapsRem /= 2;

        long long result = 0;
        for (auto it : swaps) {
            if (swapsRem == 0)   break;
            long long currSwaps = it.second;
            long long reqSwaps = min(currSwaps, swapsRem);
            swapsRem -= reqSwaps;
            
            /*
            you either go with a direct swap
            for example, minimum is min
            and the current elements are a and b
            you will directly swap a with b and take the min(a, b) as cost
            or else, you do two swaps, like a with min and b with min
            and take min * 2 as the current cost
            */
            result += min(2L * reqSwaps * minEle, reqSwaps * it.first);
        }

        return result;
    }
};

Good luck.