Intersection of Multiple Arrays

Intuition

A value belongs to the intersection exactly when it shows up in all k inner arrays. Because every inner array holds distinct values, counting how many arrays contain a value is identical to counting its total occurrences across the whole 2D input. We tally each value in a hash map, or in a fixed-size count array since values are bounded by 1000, then keep only the values whose tally equals k. Iterating the bounded value range in ascending order, or sorting the collected values, produces the required output. This runs in linear time over the total number of elements.

Algorithm walkthrough

1. 1Initialize a counter keyed by value.
2. 2For each inner array, increment the counter once for every value it contains.
3. 3Let k be the number of inner arrays.
4. 4Collect every value whose count equals k, meaning it appeared in all arrays.
5. 5Sort the collected values ascending, or iterate the bounded value range in order.
6. 6Return the resulting list.

Implementation

class Solution:
    def intersection(self, nums: list[list[int]]) -> list[int]:
        count = {}
        for arr in nums:
            for x in arr:
                count[x] = count.get(x, 0) + 1

        k = len(nums)
        result = [x for x, c in count.items() if c == k]
        result.sort()
        return result