Intersection of Multiple Arrays

Easy
753.

Intersection of Multiple Arrays

Intersection of Multiple Arrays is an easy coding problem on arrays, hash table and counting, asked in Amazon, TCS and Infosys interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var intersection = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Intersection of Multiple Arrays — Problem & Solution

Intersection of Multiple Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Intersection of Multiple Arrays is an easy coding problem on arrays, hash table and counting, asked in Amazon, TCS and Infosys interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table, Counting
  • Asked at: Amazon, TCS, Infosys
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Intersection of Multiple Arrays

  1. Hint 1

    Count, for each value, in how many distinct lists it appears.

  2. Hint 2

    Deduplicate within each list first, or a repeated value inflates its count.

  3. Hint 3

    A value belongs to the answer exactly when its count equals the number of lists.

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))

Java

public static int[] intersection(int[][] nums) {
    int[] count = new int[1001];
    for (int[] row : nums) {
        boolean[] seen = new boolean[1001];
        for (int v : row) {
            if (seen[v]) continue;
            seen[v] = true;
            count[v]++;
        }
    }
    List<Integer> out = new ArrayList<>();
    for (int v = 1; v <= 1000; v++) {
        if (count[v] == nums.length) out.add(v);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < out.size(); i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> intersection(vector<vector<int>>& nums) {
    vector<int> count(1001, 0);
    for (auto& row : nums) {
        vector<bool> seen(1001, false);
        for (int v : row) {
            if (seen[v]) continue;
            seen[v] = true;
            count[v]++;
        }
    }
    vector<int> out;
    for (int v = 1; v <= 1000; v++) {
        if (count[v] == (int) nums.size()) out.push_back(v);
    }
    return out;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets