Intersection of Multiple Arrays — Easy Problem & Solution

Problem statement

Given a list of integer arrays, return the values that appear in every one of them, sorted in ascending order.

If no value is common to all, return [].

Example 1

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation: 3 and 4 appear in all three lists.

Example 2

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation: The lists are disjoint.

Example 3

Input: nums = [[7,7,7]]
Output: [7]
Explanation: With one list, every distinct value qualifies.

Constraints

• 1 <= nums.length <= 1000
• 1 <= nums[i].length <= 1000
• 1 <= nums[i][j] <= 1000

How to solve Intersection of Multiple Arrays

Membership in the intersection is a per-value count: a value is common to all when the number of lists containing it equals the number of lists. Deduplicating within each list is what makes the count meaningful.

Approach

1. For each list, walk it while deduplicating, and increment a global tally per distinct value.
2. Collect the values whose tally equals nums.length.
3. Sort the result ascending.

Why it works

The tally counts lists, not occurrences, so a value repeated inside one list still contributes 1. Reaching the full count therefore means the value appeared in every list.

Complexity

• Time — O(total elements + V log V)
• Space — O(V)

Pitfalls

• Counting raw occurrences lets a value repeated three times in one list masquerade as appearing in three lists.
• Returning the values in insertion order rather than sorted.
• The values are bounded by 1000, so a counting array is simpler than a hash map here.

Reference solution

Python

from typing import List

def intersection(nums: List[List[int]]) -> List[int]:
    count = {}
    for row in nums:
        for v in set(row):
            count[v] = count.get(v, 0) + 1
    return sorted(v for v, c in count.items() if c == len(nums))

JavaScript

var intersection = function(nums) {
    var count = {};
    for (var r = 0; r < nums.length; r++) {
        var seen = {};
        for (var i = 0; i < nums[r].length; i++) {
            var k = String(nums[r][i]);
            if (seen[k] === true) continue;
            seen[k] = true;
            count[k] = (count[k] === undefined ? 0 : count[k]) + 1;
        }
    }
    var out = [];
    var keys = Object.keys(count);
    for (var j = 0; j < keys.length; j++) {
        if (count[keys[j]] === nums.length) out.push(Number(keys[j]));
    }
    out.sort(function(a, b) { return a - b; });
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy