#2248

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Intersection of Multiple Arrays

Find integers that are common across all arrays in a given list of arrays.

Problem Statement

You are given a 2D array of integers nums, where each subarray represents a list of integers. Your task is to find all the integers that appear in every subarray. Return the list of integers in any order.

Each subarray contains only unique integers, and the total number of integers across all subarrays is at most 1000. Your solution should aim to be efficient and consider hashing to handle array scanning and lookups.

Examples

Example 1

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]

Output: [3,4]

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: []

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.

Solution Approach

Array Scanning and Hashing

Scan through each subarray, maintaining a count of how many times each integer appears. Use a hash table to store the occurrences and check for integers that appear in every subarray.

Optimizing with Hash Map

Instead of iterating through each array multiple times, use a hash map to track the frequency of each number across all subarrays. Only return numbers with a frequency equal to the number of subarrays.

Sorting and Intersection

Sort the subarrays and use set intersections to efficiently find the common elements. This avoids the overhead of counting and makes the solution simpler in some cases.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity depends on the method used. If using array scanning and hash lookups, the time complexity is O(n * m) where n is the number of subarrays and m is the average length of each subarray. Space complexity can be O(n * m) due to storing the counts in a hash table. Sorting-based solutions may have a time complexity of O(n log n).

What Interviewers Usually Probe

Strong candidates will use a hash table to efficiently count occurrences and check common elements.
Look for solutions that optimize the time complexity using sorting or direct set operations.
Candidates should demonstrate an understanding of array scanning and hash table usage.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the case where no common elements exist, leading to incorrect results.
Not efficiently handling large inputs, causing time or space complexity issues.
Misusing sorting or set operations that increase the problem's complexity unnecessarily.

Follow-up variants

Change the problem to find common elements that appear in at least half the subarrays.
Alter the problem to return only those common elements that appear more than once in each subarray.
Modify the problem to require returning the common elements in sorted order.

FAQ

What is the best approach for solving the Intersection of Multiple Arrays problem?

The most efficient solution uses array scanning along with a hash table to track the frequency of each integer. Elements with a frequency equal to the number of subarrays are common.

Can the solution for the Intersection of Multiple Arrays problem be optimized further?

Yes, sorting the subarrays and using set intersections can sometimes simplify the solution. Hash maps generally offer better time complexity for large inputs.

What is the time complexity of solving the Intersection of Multiple Arrays problem?

The time complexity is O(n * m) for the array scanning with hash map approach, where n is the number of subarrays and m is the average length of the subarrays.

How do hash tables help in solving the Intersection of Multiple Arrays problem?

Hash tables allow you to efficiently count the occurrences of each integer across subarrays, helping to identify common integers quickly.

What if there are no common elements in the Intersection of Multiple Arrays problem?

In that case, the correct output would be an empty list, as there are no integers appearing in every subarray.

terminal

Solution

Solution 1: Counting

Traverse the array `nums`. For each sub-array `arr`, count the occurrence of each number in `arr`. Then traverse the count array, count the numbers that appear as many times as the length of the array `nums`, which are the answers.

1

2

3

4

5

6

7

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        cnt = [0] * 1001
        for arr in nums:
            for x in arr:
                cnt[x] += 1
        return [x for x, v in enumerate(cnt) if v == len(nums)]

Solution 2

#### Python3

1

2

3

4

5

6

7

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        cnt = [0] * 1001
        for arr in nums:
            for x in arr:
                cnt[x] += 1
        return [x for x, v in enumerate(cnt) if v == len(nums)]

Continue Practicing

#2225 find players with zero or one losses #1782 count pairs of nodes #1481 least number of unique integers after k removals