Rearranging Fruits

For this question, the first important part to realise is that for an equal rearragement of fruit to be possible, the must be an even count of each fruit present in each basket.

• therefore, the first part of my algorithm consists of just summing the parity of every fruit cost

Then, if a valid rearragement does exist and a fruit is misplaced on one side, it implies that there also exists a misplaced fruit on the other side. Without loss of generality, we can denote any two misplaced fruits on opposing sides as x and y, and assume that the cost of x < y. That means for each misplaced fruit, we have 2 possible options.

1. swap x and y, with a total cost of min(x, y) = x
2. swap x and y using a fruit of minimum cost, a, with a total cost of 2 * a
   • assume that there exists a fruit with minimum cost of a.
   • wlog, let us assume that it lies on the same side of x and opposite y. Then, we can simply undergo 2 operations; 1st swaps a and y, and 2nd swaps a and x

Therefore, our algorithm becomes greedy where, for each misplaced fruit, we simply choose one of 2 possible options to rearrange our fruit.

code

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        unordered_map<int, int> mp;
        int paritySum = 0;
        int minVal = INT32_MAX;
        for (int& fruit : basket1) {
            ++mp[fruit];
            if (mp[fruit] % 2 == 1) {
                ++paritySum;
            } else {
                --paritySum;
            }
            minVal = min(minVal, fruit);
        }

        for (int& fruit : basket2) {
            --mp[fruit];
            if (abs(mp[fruit]) % 2 == 1) {
                ++paritySum;
            } else {
                --paritySum;
            }
            minVal = min(minVal, fruit);
        }

        if (paritySum != 0) {
            return -1;
        }

        int count = 0;
        vector<pair<int, int>> toMove;
        for (auto& [key, value] : mp) {
            if (value != 0) {
                toMove.emplace_back(key, abs(value));
                count += abs(value);
            }
        }
        count /= 4;
        sort(toMove.begin(), toMove.end());

        int index = 0;
        long long ans = 0;
        while(count > 0) {
            ans += (long long)min(2*minVal, toMove[index].first) * (long long)min(count, toMove[index].second/2);
            count -= min(count, toMove[index].second/2);
            ++index;
        }

        return ans;
    }
};

complexity

• Time: O(n log(n)) where n is equal to the number of elements inside basket1 and basket2
• Space: O(1)

time taken

• 30 minutes and 38 seconds