350. Intersection of Two Arrays II

Problem

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

Example 1:

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

Example 2:

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

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Thought Process

  • unlike 349, this problem requires each element appear as it shows in original arrays
  • use a dict to store number count, (which I believe is similar to map in C++)
  • for num in nums1, if num exists in nums2 and
    • num does not exist in count, count[num] = 1
    • if num already exits in count, count[num] += 1
    • also it’s important to remove the num from nums2 for each iteration to avoid double count
  • return a result that has num (key) * appearance (value)

White Board

Below is the white board:

Code

class Solution:
    def intersection(self, nums1, nums2):
        res_d = {}
        res_l = []

        for num in nums1:
            if num in nums2:
                nums2.remove(num)
                if num in res_d:
                    res_d[num] += 1
                else:
                    res_d[num] = 1

        for num in res_d:
            res_l.extend([num] * res_d[num])

        return res_l


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

test_inter()
[2]

Complexity

  • In cpython, a dictionary is implemented with a hash table, with average time complexity of O(1); a major disadvantage of hash tables is losing the order
  • Time complexity is O(n), as one iteration is needed
  • Space complexity is O(n), as I created both a dict and list to store results

Optimization

If both arrays are ordered, then no need to use built in ds, create two pointers:

  • if nums[i] == nums[j]
    • if nums[i] in res, res[nums[i]] += 1
    • if nums[i] not in res, res[nums[i]] = 1
    • i += 1
    • j += 1
  • if nums[i] < nums[j]
    • i += 1
    • j stays
  • if nums[i] > nums[j]
    • j += 1
    • i stays


class Solution2:
    def inter_ord(self, nums1, nums2):
        idx, jdx = 0, 0
        res = {}
        res_l = []
        nums1, nums2 = sorted(nums1), sorted(nums2)
        # make sure input arrays are sorted
        # sorted method has a complexity of O(nlogn)

        while idx < len(nums1) and jdx < len(nums2):
            if nums1[idx] == nums2[jdx]:
                if nums1[idx] in res:
                    res[nums1[idx]] += 1
                else:
                    res[nums1[idx]] = 1
                idx += 1
                jdx += 1

            elif nums1[idx] < nums2[jdx]:
                idx += 1
            else:
                jdx += 1

        for k in res:
            res_l.extend([k] * res[k])

        return res_l

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

test_inter2()
[4, 9, 9]

We need to sort the arrays first, in python the time complexity for sorted method is O(nlogn), space complexity is O(n) as we need additional ds to store the results.