Teaching Kids Programming – Two Array Intersection Algorithms

Teaching Kids Programming: Videos on Data Structures and Algorithms

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]

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

Follow up:
What if the given array is already sorted? How would you optimize your algorithm?
What if nums1’s size is small compared to nums2’s size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Compute the Intersection of Two Arrays using Hash Maps

We can count the number of the each elements in the array and store it in hash maps, and then going through one hash map, and check if the same key appears in the second hash map. Adding the element the less number of time that appears in both array.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n1 = Counter(nums1)
        n2 = Counter(nums2)
        ans = []
        for i in n1:  # going through each unique number in array 1
            if i in n2: # check if it also appears in the second array
                for _ in range(min(n1[i], n2[i])): # min appearing time
                    ans.append(i)
        return ans            

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n1 = Counter(nums1)
        n2 = Counter(nums2)
        ans = []
        for i in n1:  # going through each unique number in array 1
            if i in n2: # check if it also appears in the second array
                for _ in range(min(n1[i], n2[i])): # min appearing time
                    ans.append(i)
        return ans            

Space complexity is O(N+M) and time complexity is O(N+M).

Compute the Intersection of Two Arrays by Sorting

If we sort two arrays, we can apply two pointer algorithm to compute the intersection of two arrays. Sorting takes O(NLogN) time and going through both arrays requires O(N) time:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        ans = []
        i = j = 0
        n1, n2 = len(nums1), len(nums2)
        while i < n1 and j < n2:
            if nums1[i] == nums2[j]:
                ans.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return ans

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        ans = []
        i = j = 0
        n1, n2 = len(nums1), len(nums2)
        while i < n1 and j < n2:
            if nums1[i] == nums2[j]:
                ans.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return ans

Space complexity is O(1) constant.

This is similar to: Teaching Kids Programming – Algorithms to Compute the Intersection of Two Linked Lists

–EOF (The Ultimate Computing & Technology Blog) —