Intersection of Multiple Arrays
Description
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 all three arrays are 3 and 4, returned in sorted order.
Example 2:
Input: nums = [[1, 2, 3], [4, 5, 6]]
Output: []
Explanation: There are no integers present in both arrays, so the result is empty.
Example 3:
Input: nums = [[7, 8, 9]]
Output: [7, 8, 9]
Explanation: With only one array, all its elements are trivially in "all" arrays.
Constraints
1 <= nums.length <= 10001 <= nums[i].length <= 10001 <= nums[i][j] <= 1000All the values of nums[i] are unique
Complexity
Show Complexity
- Time:
O(n * m) where n = number of arrays, m = avg array length - Space:
O(k) where k = total unique elements
Hints
Show Hints
- Pattern
- Counting frequency with hash map
- Approach
- Count each number's frequency. If frequency equals number of arrays, include in result. Sort before returning.
- Complexity
- Count occurrences of each number across all arrays
Solutions
Show PY Solution
def solution(nums: list[list[int]]) -> list[int]:
if len(nums) == 1:
return nums[0]
m = {}
for i in range(len(nums)):
for j in range(len(nums[i])):
v = nums[i][j]
if v not in m:
m[v] = 0
m[v] += 1
result = []
for k, v in m.items():
if v == len(nums):
result.append(k)
return sorted(result)