349. Intersection of Two Arrays

Problem

  • Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Note:

  • Each element in the result must be unique.
  • The result can be in any order.

Thought Process

  • use a dict to store number count
  • for num in nums1, if num exists in nums2 and num does not exist in count, count[num] = 1
  • for num in nums2, if num exists in nums1 and num does not exist in count, count[num] = 1
  • return only count keys

White Board

Below is the white board, and note the 2nd loop is not necessary

Code

class Solution:
    def intersection(self, nums1, nums2):
        res = {}
        for num in nums1:
            if num in nums2 and num not in res:
                res[num] = 1
        return list(res.keys())

def test_inter():
    # nums1 = [1, 2, 2, 1]
    # nums2 = [2, 2]
    nums1 = [4,9,5]
    nums2 = [9,4,9,8,4]
    inter = Solution().intersection(nums1, nums2)
    print(inter)


test_inter()
[4, 9]

Complexity

  • Time complexity is O(n * m), as one iteration is needed, within the loop check in takes O(m)
  • Space complexity is O(k), k is the size of intersection, as I created a dict(HashTable)

Optimization

Can simplify it with python built in set ds

class Solution2:
    def intersection2(self, nums1, nums2):
        set1, set2 = set(nums1), set(nums2)
        return list(set1 & set2)

def test_inter2():
    # nums1 = [1, 2, 2, 1]
    # nums2 = [2, 2]
    nums1 = [4,9,5]
    nums2 = [9,4,9,8,4]
    inter = Solution2().intersection2(nums1, nums2)
    print(inter)

test_inter2()
[9, 4]

In cpython, set is implemented with hash tables. The time complexity for dict intersection is O(min(len(nums1), len(nums2))), but space complexity is O(n).