Crate digging

Two collectors want to trade spares. A set intersection answers the wrong question, because three copies of the same single are three different trades.

The problem

At a record fair two dealers put their spare seven-inch singles on the table. Every single carries a catalogue number, and a dealer can hold several copies of the same number. A trade is one record for one record with the same catalogue number, so if the first dealer has three copies of 412 and the second has two, exactly two trades of 412 can happen and one copy stays on the table.

List every catalogue number that changes hands, once per trade, in ascending order. Neither crate is in any particular order to begin with.

Input. crate_a, crate_b — two lists of integers, the catalogue numbers in each dealer's crate. Duplicates are meaningful and the lists are unsorted.

Output. The catalogue numbers traded, one entry per trade, ascending.

Example.

crate_a = [412, 91, 412, 7, 91], crate_b = [91, 412, 412, 412]   ->  [91, 412, 412]

The first dealer has two 412s, the second has three, so two trades of 412. Both have 91, but the first has two copies and the second one, so one trade of 91. The single 7 has no partner.

A second example, where extra copies on one side buy nothing:

crate_a = [55, 55, 55], crate_b = [55]   ->  [55]
crate_a = [3, 9],       crate_b = [4, 8]   ->  []

Three copies against one still makes exactly one trade, and two crates that share nothing produce an empty list rather than an error.

Constraints.

• 0 <= len(crate_a), len(crate_b) <= 10^5
• 1 <= catalogue number <= 10^6
• Either crate may be empty.

Hints

Approach

Brute force

For each record in the first crate, scan the second for an unclaimed copy and mark it claimed. That is up to len(crate_a) * len(crate_b) comparisons — 10¹⁰ for two full crates — plus the bookkeeping to stop one record being traded twice.

The insight

Sort both crates once and the matching collapses into a single merge: at every step the smaller of the two numbers under the fingers can never be matched again, so it is discarded and never looked at twice.

The precondition is order. Once both lists are non-decreasing, everything ahead of a finger is greater than or equal to what it points at. So if crate_a[i] is strictly less than crate_b[j], no record left in the second crate can equal it, and advancing i loses nothing. Equal values are a trade, and advancing both fingers is exactly the "one copy each" rule that makes duplicates come out right.

Algorithm

1. Sort both crates ascending.
2. Set i = 0, j = 0, and an empty result list.
3. While both fingers are in range: if crate_a[i] < crate_b[j], advance i; if it is greater, advance j.
4. Otherwise the numbers match — append it and advance both fingers.
5. Stop when either crate runs out; the result is already ascending.

Complexity

Time O(n log n + m log m) — the two sorts dominate; the merge itself is a single O(n + m) pass. Space O(n + m) for the sorted copies, or O(1) beyond the output if you are allowed to sort in place.

A hash count of one crate answers the same question in O(n + m) time. The merge wins when the crates arrive sorted already, or when they are too large to hold in memory and can only be streamed past each other.

Solution

"""Crate digging — multiset intersection by merging two sorted crates."""


def solve(crate_a, crate_b):
    left = sorted(crate_a)
    right = sorted(crate_b)
    i = j = 0
    traded = []
    # Invariant: every trade among left[:i] and right[:j] has already been
    # recorded, so whichever finger points at the smaller number is finished.
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            i += 1
        elif left[i] > right[j]:
            j += 1
        else:
            traded.append(left[i])   # one copy each leaves the crates
            i += 1
            j += 1
    return traded

TESTS = [
    (([412, 91, 412, 7, 91], [91, 412, 412, 412]), [91, 412, 412]),
    (([55, 55, 55], [55]), [55]),
    (([3, 9], [4, 8]), []),
    (([], [1, 2]), []),
    (([4, 4, 4, 4], [4, 4]), [4, 4]),
    (([1, 2, 3], [3, 2, 1]), [1, 2, 3]),
]

Pitfalls

• Returning each number once. A set intersection gives [91, 412] for the first example when two 412s trade. The multiplicity is the answer, not noise.
• Advancing both fingers on a mismatch. With crate_a = [2, 5] and crate_b = [5], stepping both past the 2-versus-5 disagreement runs j off the end and reports no trades at all instead of one.
• Merging without sorting. The merge is only correct because everything ahead of a finger is larger; on raw crates it silently drops matches.
• Guarding the loop on one index. An empty crate, or an early exhaustion, needs both i and j checked before either is read.

Variants

• Micron drift — two pointers on a single list, moving inward rather than two lists moving forward.
• Hull trim — sorting first for the same reason, then using the order to prune instead of to merge.