Intersection Of Multiple Arrays - Leetcode Solution

The Intersection Of Multiple Arrays problem on LeetCode requires finding the common elements in multiple arrays.

To solve this problem, one approach is to use a hash map to store the counts of each element in all arrays. For each element in the first array, increment its count in the hash map. Then, for every subsequent array, decrement the count of each element in the hash map that is not present in the current array.

Finally, any element in the hash map with a count equal to the number of input arrays is a common element in all arrays.

Here is the code to implement this algorithm in Python:

from collections import defaultdict

def intersect(arrays):
    counts = defaultdict(int)
    for element in arrays[0]:
        counts[element] += 1
    for array in arrays[1:]:
        for element in counts:
            if element not in array:
                counts[element] -= 1
    common = []
    for element in counts:
        if counts[element] == len(arrays):
            common.append(element)
    return common

The input arrays is a list of arrays. The function intersect first initializes a hash map counts using defaultdict with initial value of 0. It then loops through every element in the first array and increments its count in counts. The second loop goes through every subsequent array and decrements the count of any element in counts that is not present in the current array.

After that, common is initialized as an empty list. The last loop goes through every element in counts and any element with a count equal to the number of input arrays is added to common.

The time complexity of this algorithm is O(nk), where n is the total number of elements in all arrays and k is the number of arrays. The space complexity is also O(n), which is the size of the hash map.

1