0602HardArrayHash TableGreedySort

Matching Two Casting Bins

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_cost(basket1: list[int], basket2: list[int]) -> int:

Java

public long minCost(int[] basket1, int[] basket2)

The intended approach

Time O(n log n): counting is linear and sorting the castings that must move dominates.Space O(n) for the counts and the list of castings that must move.

Count every die code across both bins. A code appearing an odd number of times can never be split evenly, which rules the job out. Otherwise each bin should end up with half the copies of each code, and the difference between what a bin holds and what it should hold says exactly which castings must leave it; gather all those castings into one list. Each exchange retires one casting from each direction, so exactly half the gathered list gets billed. A casting can either be traded straight across, billed at its own code, or routed through the cheapest casting on the line in two exchanges, billed at twice that code. Sorting the gathered list and billing its cheaper half at the smaller of those two prices gives the minimum.

Pythonentry point: min_cost

def min_cost(basket1, basket2):
    # O(n log n) time from sorting the castings that have to move, O(n) space.
    total_count = {}
    for code in basket1:
        total_count[code] = total_count.get(code, 0) + 1
    for code in basket2:
        total_count[code] = total_count.get(code, 0) + 1
    for code in total_count:
        if total_count[code] % 2:
            return -1
    held = {}
    for code in basket1:
        held[code] = held.get(code, 0) + 1
    movers = []
    for code in total_count:
        gap = held.get(code, 0) - total_count[code] // 2
        if gap < 0:
            gap = -gap
        for _ in range(gap):
            movers.append(code)
    movers.sort()
    cheapest = basket1[0]
    for code in basket1:
        if code < cheapest:
            cheapest = code
    for code in basket2:
        if code < cheapest:
            cheapest = code
    relay = 2 * cheapest
    total = 0
    # Half of the movers travel one way and half the other, so exactly half of
    # them can be the one charged for; charge the cheaper half.
    for i in range(len(movers) // 2):
        total += movers[i] if movers[i] < relay else relay
    return total

The obvious version

Work out which castings must leave the first bin and which must leave the second; the two lists are the same length. Then try every way of pairing one list against the other, billing a pair at the cheapest of a direct trade or a two-exchange route through the cheapest casting on the line, and keep the least total.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_cost(basket1, basket2):
    total_count = {}
    for code in basket1:
        total_count[code] = total_count.get(code, 0) + 1
    for code in basket2:
        total_count[code] = total_count.get(code, 0) + 1
    for code in total_count:
        if total_count[code] % 2:
            return -1
    held1 = {}
    for code in basket1:
        held1[code] = held1.get(code, 0) + 1
    leaving1 = []
    leaving2 = []
    for code in total_count:
        want = total_count[code] // 2
        got = held1.get(code, 0)
        if got > want:
            for _ in range(got - want):
                leaving1.append(code)
        elif got < want:
            for _ in range(want - got):
                leaving2.append(code)
    cheapest = basket1[0]
    for code in basket1:
        if code < cheapest:
            cheapest = code
    for code in basket2:
        if code < cheapest:
            cheapest = code
    relay = 2 * cheapest
    best = [None]
    taken = [False] * len(leaving2)

    def walk(idx, running):
        if best[0] is not None and running >= best[0]:
            return
        if idx == len(leaving1):
            if best[0] is None or running < best[0]:
                best[0] = running
            return
        for j in range(len(leaving2)):
            if taken[j]:
                continue
            here = leaving1[idx]
            there = leaving2[j]
            price = here if here < there else there
            if relay < price:
                price = relay
            taken[j] = True
            walk(idx + 1, running + price)
            taken[j] = False

    walk(0, 0)
    if best[0] is None:
        return 0
    return best[0]

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in