Teaching Kids Programming – Intersection of Multiple Arrays (Set and Counter)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array of nums sorted in ascending order.

Example 1:
Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation:
The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

Example 2:
Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation:
There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

Constraints:
1 <= nums.length <= 1000
1 <= sum(nums[i].length) <= 1000
1 <= nums[i][j] <= 1000
All the values of nums[i] are unique.

Array Intersection Algorithm via Set

Construct a set from the first list, then intersect all the other lists.

1
2
3
4
5
6
7
8

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        if not nums:
            return []
        a = set(nums[0])
        for i in nums[1:]:
            a = a & set(i)
        return sorted(a)

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        if not nums:
            return []
        a = set(nums[0])
        for i in nums[1:]:
            a = a & set(i)
        return sorted(a)

Time/Space complexity O(N) where N is the total number of elements from all list.

Array Intersection Algorithm via Counter

Each array does not contain duplicate numbers, thus, if a number appears N time, then it appears in all lists. We can use Counter to do the counting. The counter.update method allows us to take new accumulate changes from another Counter.

1
2
3
4
5
6
7

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        n = len(nums)
        c = Counter()
        for i in nums:
            c.update(Counter(i))       
        return sorted(i for i, j in c.items() if j == n)

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        n = len(nums)
        c = Counter()
        for i in nums:
            c.update(Counter(i))       
        return sorted(i for i, j in c.items() if j == n)

Then, we get all the numbers that appear N times. Time/Space complexity is the same O(N).

–EOF (The Ultimate Computing & Technology Blog) —