Shared Values Of Two Lists
Problem
Given two lists of values, return the values that occur in both of them. Each shared value appears once in the result even when either list repeats it, and the result follows the order in which the values first show up in the first list.
Examples
Input: a = [1, 2, 2, 1], b = [2, 2]
Output: [2]
Why: a shared value is reported once no matter how often it repeatsInput: a = [4, 9, 5], b = [9, 4, 9, 8, 4]
Output: [4, 9]
Why: the order comes from the first list, not the secondInput: a = [1, 2], b = [3]
Output: []
Why: edge case, the lists have nothing in commonHints
0 / 3
Comparing each value of the first list against the whole second list gives the right answer with far too much rereading. Ask what you could prepare once, before the comparison starts.
The question asked at every element of the first list is a membership test against the second list, and there is a structure whose whole job is answering that in constant time.
Load the second list into a set. Walk the first list once, and keep a value when the set contains it and you have not already reported it. Track what you have reported in a second set so duplicates in the first list do not produce duplicate output.
Solution
Loading the second list into a set turns each of the n comparisons into a constant-time lookup instead of a scan. Walking the first list in order means the output order falls out for free, and a second set of already-reported values keeps repeats out without sorting or post-processing. Time is O(n + m) on average, and space is O(m) for the lookup set plus the reported values.
def shared_values(a, b):
pool = set(b) # membership in b is now a constant-time test
out, reported = [], set()
for x in a:
if x in pool and x not in reported:
out.append(x) # first appearance in a fixes the order
reported.add(x)
return out
print(shared_values([1, 2, 2, 1], [2, 2])) # -> [2]
print(shared_values([4, 9, 5], [9, 4, 9, 8, 4])) # -> [4, 9]
print(shared_values([1, 2], [3])) # -> []Stuck on the idea rather than the code? Hash Table Basics covers it.