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 <= 1000
1 <= nums[i].length <= 1000
1 <= nums[i][j] <= 1000
All the values of nums[i] are unique

Signature

def solution(nums: list[list[int]]) -> list[int]: ...

Complexity

Time: O(n * m) where n = number of arrays, m = avg array length
Space: O(k) where k = total unique elements

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

Python

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)