Intersection of Multiple Arrays

Problem

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 ineach array of nums sorted inascending order.

Examples

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 each of nums[0] = [_**3**_ ,1,2,_**4**_ ,5], nums[1] = [1,2,_**3**_ ,_**4**_], and nums[2] = [_**3**_ ,_**4**_ ,5,6] are 3 and 4, so we return [3,4].

Example 2

Input: nums = [[1,2,3],[4,5,6]]
Output: []
Explanation: 
There does not exist any integer present both in nums[0] and nums[1], so we return an empty list [].

Constraints

• 1 <= nums.length <= 1000
• 1 <= sum(nums[i].length) <= 1000
• 1 <= nums[i][j] <= 1000
• All the values of nums[i] are unique.

Solution

Method 1 – Hash Map Counting

Intuition

We want to find elements that appear in every array. By counting the occurrences of each number across all arrays, we can select those that appear in all of them.

Approach

1. Use a hash map to count the number of arrays each integer appears in.
2. For each array, add 1 to the count for each unique integer.
3. After processing all arrays, collect integers whose count equals the number of arrays.
4. Sort the result in ascending order.

Code

C++

vector<int> intersection(vector<vector<int>>& nums) {
    unordered_map<int, int> cnt;
    int n = nums.size();
    for (auto& arr : nums) {
        for (int x : arr) cnt[x] = 0;
    }
    for (auto& arr : nums) {
        unordered_set<int> seen;
        for (int x : arr) {
            if (!seen.count(x)) {
                cnt[x]++;
                seen.insert(x);
            }
        }
    }
    vector<int> ans;
    for (auto& [k, v] : cnt) if (v == n) ans.push_back(k);
    sort(ans.begin(), ans.end());
    return ans;
}

Go

func intersection(nums [][]int) []int {
    cnt := map[int]int{}
    n := len(nums)
    for _, arr := range nums {
        for _, x := range arr {
            cnt[x] = 0
        }
    }
    for _, arr := range nums {
        seen := map[int]struct{}{}
        for _, x := range arr {
            if _, ok := seen[x]; !ok {
                cnt[x]++
                seen[x] = struct{}{}
            }
        }
    }
    ans := []int{}
    for k, v := range cnt {
        if v == n {
            ans = append(ans, k)
        }
    }
    sort.Ints(ans)
    return ans
}

Java

class Solution {
    public List<Integer> intersection(int[][] nums) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = nums.length;
        for (int[] arr : nums)
            for (int x : arr) cnt.put(x, 0);
        for (int[] arr : nums) {
            Set<Integer> seen = new HashSet<>();
            for (int x : arr) {
                if (!seen.contains(x)) {
                    cnt.put(x, cnt.get(x) + 1);
                    seen.add(x);
                }
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (var e : cnt.entrySet())
            if (e.getValue() == n) ans.add(e.getKey());
        Collections.sort(ans);
        return ans;
    }
}

Kotlin

class Solution {
    fun intersection(nums: Array<IntArray>): List<Int> {
        val cnt = mutableMapOf<Int, Int>()
        val n = nums.size
        for (arr in nums) for (x in arr) cnt[x] = 0
        for (arr in nums) {
            val seen = mutableSetOf<Int>()
            for (x in arr) {
                if (x !in seen) {
                    cnt[x] = cnt[x]!! + 1
                    seen.add(x)
                }
            }
        }
        return cnt.filter { it.value == n }.keys.sorted()
    }
}

Python

def intersection(nums: list[list[int]]) -> list[int]:
    from collections import Counter
    n = len(nums)
    cnt = Counter()
    for arr in nums:
        cnt.update(set(arr))
    ans = [k for k, v in cnt.items() if v == n]
    return sorted(ans)

Rust

use std::collections::{HashMap, HashSet};
fn intersection(nums: Vec<Vec<i32>>) -> Vec<i32> {
    let n = nums.len();
    let mut cnt = HashMap::new();
    for arr in &nums {
        for &x in arr {
            cnt.entry(x).or_insert(0);
        }
    }
    for arr in &nums {
        let mut seen = HashSet::new();
        for &x in arr {
            if seen.insert(x) {
                *cnt.get_mut(&x).unwrap() += 1;
            }
        }
    }
    let mut ans = vec![];
    for (&k, &v) in &cnt {
        if v == n {
            ans.push(k);
        }
    }
    ans.sort();
    ans
}

TypeScript

function intersection(nums: number[][]): number[] {
  const cnt: Record<number, number> = {};
  const n = nums.length;
  for (const arr of nums) for (const x of arr) cnt[x] = 0;
  for (const arr of nums) {
    const seen = new Set<number>();
    for (const x of arr) {
      if (!seen.has(x)) {
        cnt[x]++;
        seen.add(x);
      }
    }
  }
  const ans = Object.entries(cnt).filter(([_, v]) => v === n).map(([k]) => +k);
  ans.sort((a, b) => a - b);
  return ans;
}

Complexity

• ⏰ Time complexity: O(m * k + N log N) — m is the number of arrays, k is the average array length, N is the number of unique elements (for sorting).
• 🧺 Space complexity: O(N) — For the hash map and result array.