Teaching Kids Programming – Find Numbers in At Least Two Arrays Out of Three (Hash Set)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given three integer arrays nums1, nums2, and nums3, return a distinct array containing all the values that are present in at least two out of the three arrays. You may return the values in any order.

Example 1:
Input: nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
Output: [3,2]
Explanation: The values that are present in at least two arrays are:
– 3, in all three arrays.
– 2, in nums1 and nums2.

Example 2:
Input: nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
Output: [2,3,1]
Explanation: The values that are present in at least two arrays are:
– 2, in nums2 and nums3.
– 3, in nums1 and nums2.
– 1, in nums1 and nums3.

Example 3:
Input: nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
Output: []
Explanation: No value is present in at least two arrays.

Constraints:
1 <= nums1.length, nums2.length, nums3.length <= 100
1 <= nums1[i], nums2[j], nums3[k] <= 100

Hints:
What data structure can we use to help us quickly find whether an element belongs in an array?
Can we count the frequencies of the elements in each array?

Algorithms to Find Numbers in At Least Two Arrays Out of Three (Hash Set)

We can use the hash set to solve this problem. First converting each array to hash set (filter out duplicate numbers), then we use the & aka intersection operator and | aka union operator to find out the common intersection parts between each pairs. The time/space complexity is O(N) assuming each array is length of N.

1
2
3
4
5
6

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        s1 = set(nums1)
        s2 = set(nums2)
        s3 = set(nums3)        
        return s1&s2 | s2&s3 | s1&s3

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        s1 = set(nums1)
        s2 = set(nums2)
        s3 = set(nums3)        
        return s1&s2 | s2&s3 | s1&s3

The following is a manual approach which we check each element in the first array to see if it appears in the second or third array. And also, we need to find out if any number in the second array that appears in the third array.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        s1 = set(nums1)
        s2 = set(nums2)
        s3 = set(nums3)        
        ans = set()
        for i in s1:
            if i in s2 or i in s3:
                ans.add(i)
        for i in s2:
            if i in s3:
                ans.add(i)
        return ans

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        s1 = set(nums1)
        s2 = set(nums2)
        s3 = set(nums3)        
        ans = set()
        for i in s1:
            if i in s2 or i in s3:
                ans.add(i)
        for i in s2:
            if i in s3:
                ans.add(i)
        return ans

We can also use a Counter or default dictionary to manually record the number frequencies.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        c = defaultdict(int)
        for i in set(nums1):
            c[i] += 1
        for i in set(nums2):
            c[i] += 1
        for i in set(nums3):
            c[i] += 1
        return [k for k, v in c.items() if v > 1]

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        c = defaultdict(int)
        for i in set(nums1):
            c[i] += 1
        for i in set(nums2):
            c[i] += 1
        for i in set(nums3):
            c[i] += 1
        return [k for k, v in c.items() if v > 1]

Also, we can pass it to Counter constructor, and we need to return the numbers that appear at least two times.

1
2
3
4

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        c = Counter(list(set(nums1)) + list(set(nums2)) + list(set(nums3)))
        return [k for k, v in c.items() if v > 1]

class Solution:
    def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
        c = Counter(list(set(nums1)) + list(set(nums2)) + list(set(nums3)))
        return [k for k, v in c.items() if v > 1]

–EOF (The Ultimate Computing & Technology Blog) —