Intersection With Dupes

Given two slices of integers, return their multiset intersection: each value appears in the result the minimum number of times it appears in the two slices. Return the values sorted ascending (repeats allowed).

intersectionWithDupes(a, b)

Input format: a | b. Output the values, sorted, space-separated (empty line if none).

Examples

intersectionWithDupes([]int{1, 2, 2, 3}, []int{2, 2, 2})  // → [2, 2]
intersectionWithDupes([]int{1, 1}, []int{1})              // → [1]
intersectionWithDupes([]int{1, 2}, []int{3, 4})           // → []

Walkthrough

Thinking it through

This is a step up from plain intersection: you need to respect how many times each value appears, and only report it as many times as it can be matched between the two lists. A plain set only knows "present" or "absent," not "present three times" — so this needs a hash map (value to count), not a hash set.

Reasoning about what "multiset intersection" actually means

If a value appears three times in the first list and twice in the second, it can only be matched twice — the second list runs out after that. So the right output count for each value is the smaller of its two counts.

Building the approach

Count each value's occurrences in the first list, in a map.
Walk the second list. For each value, check whether the map still shows a positive remaining count.
If it does, there's still an unmatched occurrence available — emit the value, and decrement its count.
If the count has hit zero (never in the first list, or already used up), skip it.
Sort the collected results at the end.

Why decrementing is what makes the counts correct

Without the decrement, you'd just be checking "is this value present at all" — that collapses back into plain intersection and loses the count entirely, over-reporting values that appear many times in the second list. Treating the map's count as a spendable budget means each occurrence in the first list can only be consumed by one occurrence in the second — exactly the pairing multiset intersection needs.

Why this is efficient

Building the count map costs time proportional to the first list's size; walking the second list with constant-time lookups and decrements costs time proportional to its size. Total work is linear in the combined size — a big win over a brute-force search-and-mark approach between the two lists.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.