Intersection of two watchlists

Question

Two analysts each hand you a watchlist (a list of symbols that may contain repeats). Return the symbols the two lists have in common, where a symbol appears in the result as many times as it appears in both lists, that is, the minimum of its two counts.

a = ["A", "A", "B"], b = ["A", "B", "B"]
-> ["A", "B"]      # A: min(2,1)=1, B: min(1,2)=1

Return the multiset intersection. Aim for $O(m + n)$ .

Accepted Answer

Count occurrences in each list. For every symbol in the first list's counts, emit it min(counta, countb) times, where a symbol missing from the second list contributes zero. This respects multiplicities without sorting. Tracing a = ["A", "A", "B"], b = ["A", "B", "B"]: A contributes min(2, 1) = 1, B contributes min(1, 2) = 1, giving ["A", "B"]. Time O(m + n), space O(m + n) for the counters. Python's Counter even supports ca & cb to compute this intersection directly, but the explicit loop makes the min-of-counts logic clear. Result order follows first-list insertion order, not any sort. Take…

Intersection of two watchlists

Your answer

More Coding questions