Intersection of Two Arrays

1. The obvious way

   Compare every pair with nested loops: O(n x m).

2. The key insight

   Put one list into a set (lookup is one step). Walk through the other list; every value found in the set is common. Collect the answers in another set so each appears once.

3. The algorithm
   1. Make a set from the first list.
   2. Walk through the second list.
   3. Each value that is in the set goes into the answer set.
   4. Return the answer as a list.

Watch it run

set: {1, 2}

def intersection(nums1, nums2):
    known = set(nums1)               # everything the first list has
    common = set()
    for number in nums2:
        if number in known:
            common.add(number)
    return list(common)

# equivalent: list(set(nums1) & set(nums2))

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.