2561. Rearranging Fruits

Description

You have two fruit baskets containing n fruits each. You are given two 0-indexed integer arrays basket1 and basket2 representing the cost of fruit in each basket. You want to make both baskets equal. To do so, you can use the following operation as many times as you want:

• Choose two indices i and j, and swap the i fruit of basket1 with the j fruit of basket2.
• The cost of the swap is min(basket1[i], basket2[j]).

Two baskets are considered equal if sorting them according to the fruit cost makes them exactly the same baskets.

Return the minimum cost to make both the baskets equal or -1 if impossible.

 

Example 1:

Input: basket1 = [4,2,2,2], basket2 = [1,4,1,2]
Output: 1
Explanation: Swap index 1 of basket1 with index 0 of basket2, which has cost 1. Now basket1 = [4,1,2,2] and basket2 = [2,4,1,2]. Rearranging both the arrays makes them equal.

Example 2:

Input: basket1 = [2,3,4,1], basket2 = [3,2,5,1]
Output: -1
Explanation: It can be shown that it is impossible to make both the baskets equal.

 

Constraints:

• basket1.length == basket2.length
• 1 <= basket1.length <= 105
• 1 <= basket1[i], basket2[i] <= 109

 

Solutions

Solution: Greedy + Hash Table

• Time complexity: O(n+queries.length)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} basket1
 * @param {number[]} basket2
 * @return {number}
 */
const minCost = function (basket1, basket2) {
  const costMap = new Map();
  const costs = [];
  let swapCount = 0;

  for (const cost of basket1) {
    const count = costMap.get(cost) ?? 0;

    costMap.set(cost, count + 1);
  }

  for (const cost of basket2) {
    const count = costMap.get(cost) ?? 0;

    costMap.set(cost, count - 1);
  }

  for (const [cost, count] of costMap) {
    if (count % 2 !== 0) return -1;

    costs.push({ cost, count: Math.abs(count) / 2 });

    if (count > 0) {
      swapCount += count / 2;
    }
  }

  costs.sort((a, b) => a.cost - b.cost);

  const minCost = costs[0].cost;
  let result = 0;

  for (const { cost, count } of costs) {
    const swap = Math.min(swapCount, count);
    const cost1 = minCost * swap * 2;
    const cost2 = cost * swap;

    result += Math.min(cost1, cost2);
    swapCount -= swap;

    if (!swapCount) return result;
  }

  return -1;
};