Problem overview
The method intersection receives two lists of integers, first and second, and returns the numbers that appear in both. Each shared number appears once in the result, however many times it occurs in the inputs, and the result is sorted from smallest to largest. Each list has between 1 and 1000 elements, with values from -1000 to 1000.
For first = [1, 2, 2, 1] and second = [2, 2] the result is [2]. For first = [4, 9, 5] and second = [9, 4, 9, 8, 4] the result is [4, 9]: both numbers occur in both lists, and although each appears twice in second, it is listed once.
Approach: remember one list, scan the other
The brute-force solution checks every element of one list against every element of the other, which costs O(n * m). Checking whether a number is in a list is slow. Checking whether a number is a key of a dictionary is fast, on average O(1), so the idea is to put one list into a dictionary and scan the other list against it.
The dictionary maps each number of the first list to a counter that starts at 0. The scan through the second list adds one to the counter of every number it finds in the dictionary and ignores numbers that aren't there. When the scan ends, a number whose counter is above 0 occurred in both lists. A dictionary has only one key per number, so duplicates collapse on their own, and the result never repeats a number.
The code first makes sure the dictionary is built from the shorter list. That keeps the dictionary small, so the extra space is O(min(n, m)). Which list is stored doesn't change the answer, because intersection is symmetric.
The time limit of O(n + m) excludes the last step. The numbers shared by both lists are collected in the dictionary's order, which is the order they were first stored, and the expected answer is ascending, so the result list is sorted at the end.
Step by step
- Give the lists short names.
nums1andnums2start out asfirstandsecond. They are only new names for the same lists, so the code can swap them without touching the parameters. - Create the dictionary
d. Its keys will be numbers fromnums1, and its values will count matches innums2. - Make
nums1the shorter list. If it is longer thannums2, the two names are swapped. - Store the shorter list. The first loop goes through
nums1. - Set each counter to 0. A repeated number is simply set to 0 again, so each key exists once.
- Scan the longer list with a second loop over
nums2. - Skip strangers. A number that isn't a key of
dis not in the shorter list, socontinuemoves on to the next number. - Count matches. For a number that is a key, the
elsebranch adds one to its counter. - Start the result as an empty list.
- Walk through the dictionary with
d.items(), which gives each key and its counter as a pair, unpacked intokandval. - Keep the matches. If the counter is above 0, the number was found in
nums2, so it goes into the result. - Sort and return.
result.sort()puts the list in ascending order, and the method returns it.
The solution in Python
class Solution:
def intersection(self, first: List[int], second: List[int]) -> List[int]:
nums1, nums2 = first, second
d = {}
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
for i in nums1:
d[i] = 0
for i in nums2:
if i not in d:
continue
else:
d[i] = d[i] + 1
result = []
for k, val in d.items():
if val > 0:
result.append(k)
result.sort()
return result
Python details worth knowing:
- Dictionaries keep insertion order.
d.items()yields the pairs in the order the keys were first stored. If the stored list is[9, 4, 5], that is 9, 4, 5, not ascending, which is why the finalsort()is needed. sort()returnsNone.result.sort()sorts the list in place, so the next line returnsresult. Writingreturn result.sort()would returnNone.inon a dictionary tests keys.i not in dis a hash lookup, not a scan of values.- Swapping names.
nums1, nums2 = nums2, nums1exchanges what the two names refer to. No list is copied, andfirstandsecondare not changed. - Any hashable value works as a key. Integers, including negative ones, are valid dictionary keys.
Complexity
Time: O(n + m) plus the sort. Building the dictionary and scanning the other list each take one pass with average O(1) lookups, and reading the dictionary is a pass over at most min(n, m) keys. Sorting k shared numbers costs O(k log k).
Space: O(min(n, m)). The dictionary holds one key per distinct number of the shorter list, and the result holds at most as many numbers.
Edge cases and common mistakes
- No common numbers. For
[1]and[2]every counter stays 0, and the result is the empty list[]. - Duplicates.
[1, 2, 2, 1]and[2, 2]give[2]. The counter for 2 reaches 2, but the number is added once. - Negative numbers and zero. They work like any other keys, and the sorted result places negatives first.
- Testing the counter as truthy. A counter of 0 means "not found", so the code compares
val > 0. Checking only that the key exists would include every number of the shorter list. - Forgetting the sort. The answer may come out in the right numbers but the wrong order, such as
[9, 4]instead of[4, 9]forfirst = [9, 4]andsecond = [4, 9, 5].
Testing
first = [1, 2, 2, 1],second = [2, 2]gives[2].first = [4, 9, 5],second = [9, 4, 9, 8, 4]gives[4, 9].first = [1],second = [2]gives[].
