EasyArrayHash TableCountingSorting

Intersection of Multiple Arrays

1 approach, code in every language

You are given a two-dimensional array nums of positive integers. Every inner array contains a set of distinct values (no duplicates within a single inner array).

Return a sorted list, in ascending order, of the integers that appear in every inner array of nums.

If no integer is present in all of the inner arrays, return an empty list.

Example 1

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

Output: [3,4]

Only 3 and 4 appear in all three inner arrays, so the sorted intersection is [3,4].

Example 2

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

Output: []

No value is shared between the two inner arrays, so the result is empty.

Constraints

1 <= nums.length <= 1000
1 <= sum(nums[i].length) <= 1000
1 <= nums[i][j] <= 1000
All values within each nums[i] are distinct

Count Occurrences Across Arrays

Tally how many arrays contain each value and keep those seen in all of them.

Loading animation…

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

1Initialize a counter keyed by value.
2For each inner array, increment the counter once for every value it contains.
3Let k be the number of inner arrays.
4Collect every value whose count equals k, meaning it appeared in all arrays.
5Sort the collected values ascending, or iterate the bounded value range in order.
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

Time

O(S + V log V)

Space

O(V)

S is the total number of elements across all inner arrays and V is the number of distinct values (bounded by 1000). Counting is linear; the sort adds V log V, or is avoided entirely by scanning the bounded range in order.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free