Write common_values(a: list[int], b: list[int]) -> list[int] that returns every value appearing in both lists, each value once, in increasing order.
common_values([5, 1, 3, 3, 9], [3, 7, 5, 5]) # [3, 5]
common_values([1, 2], [3, 4]) # []
0 <= len(a), len(b) <= 2 * 10^5; values are in[-10^9, 10^9]and may repeat.- The obvious version,
[x for x in a if x in b], looks like one loop but is really two:x in bscans the whole list, so it's O(len(a) * len(b)), about 4 * 10^10 steps at the maximum size. The tests include a case that size. - Aim for O(n log n) overall (the final sort is fine).
Show hint
x in some_set is O(1) on average while x in some_list is O(n), so turn the lists into sets first.