Show problems as
Classic problem #2561HardArrayHash TableGreedySort

Rearranging Fruits

Real-world version: Matching Two Casting Bins
Tracked in this browser only
Read Rearranging Fruits on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two bins on a foundry line hold the same number of castings. basket1 and basket2 list the die code stamped on each casting, bin by bin.

An exchange picks one slot i of the first bin and one slot j of the second, then trades the two castings sitting in those slots. The exchange is billed at min(basket1[i], basket2[j]), the smaller of the two die codes involved. Any number of exchanges may be made, in any order.

The bins count as matched when, for every die code, both bins hold the same number of castings stamped with it. The order of castings inside a bin is irrelevant.

Return the smallest total bill for a series of exchanges that leaves the bins matched. Return -1 if no series of exchanges can match them. Die codes are at least 1, so a real bill is never negative and cannot be mistaken for the -1 answer.

Examples

Example 1

Input
basket1 = [10, 10, 1], basket2 = [20, 20, 1]
Output
2

Trading the casting stamped 10 with the one stamped 1 in the second bin bills 1, and trading that 1 back out against a 20 bills another 1. Both bins then hold one casting of each of 1, 10 and 20, for a total bill of 2.

Example 2

Input
basket1 = [2, 5], basket2 = [5, 2]
Output
0

Each bin already holds one casting stamped 2 and one stamped 5, so no exchange is needed and the bill is 0.

Example 3

Input
basket1 = [4], basket2 = [7]
Output
-1

Across the two bins the code 4 appears once and the code 7 appears once. A single copy cannot be present in both bins, so the answer is -1.

Constraints

  • basket1.length == basket2.length
  • 1 <= basket1.length <= 10^5
  • 1 <= basket1[i], basket2[i] <= 10^9
  • The smallest total bill never exceeds 10^14, well inside a 64-bit integer.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_cost(basket1: list[int], basket2: list[int]) -> int:
Java
public long minCost(int[] basket1, int[] basket2)

More on the same topics