Intersection of Multiple Arrays solution and explanation
9 more videos on this problem
Intersection of Multiple Arrays | Leetcode 2248 | Strings | Contest 290 🔥🔥Coding Decoded · 6:10 · 2K views
2248. Intersection of Multiple Arrays || Leetcode Weekly Contest 290 || Leetcode 2248Bro Coders · 9:15 · 2K views
2248. Intersection of Multiple Arrays | Zero to FAANG | Assignment Solution | Leetcode | StriverProgrammers Zone · 9:37 · 892 views
2248. Intersection of Multiple Arrays (Leetcode Easy)Programming Live with Larry · 3:51 · 751 views
Leetcode Weekly-contest-290 - Intersection of Multiple ArraysPrakhar Agrawal · 3:07 · 310 views
LeetCode 2248 | Intersection of Multiple Arrays | Counting Array | JavaSleepy Cracker · 3:38 · 218 views
2248 Intersection of Multiple Arrays LeetCode JavaScript HashmapSantamaria Code · 8:21 · 166 views
Intersection of Multiple Arrays LeetCode - JavaCode with Katie · 7:24 · 127 views
Leetcode 2248 - Intersection of Multiple ArraysShafik Quoraishee · 9:28 · 59 views
2248. Intersection of Multiple Arrays - Javascript - Time: O(n) Space: O(n) - LeetcodeAaron Sadino Coding · 18:08 · 48 views
The problem
nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array of nums sorted in ascending order.
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 <= 10001 <= sum(nums[i].length) <= 10001 <= nums[i][j] <= 1000- All the values of
nums[i]are unique.
Approach overview
Problem Overview: You receive a list of integer arrays. The task is to return all numbers that appear in every array. The final result must be sorted in ascending order. This is essentially computing the intersection across multiple arrays rather than just two.
Approach 1: Hash Map Counting (O(N) time, O(U) space)
This approach counts how many arrays contain each value. Iterate through every number in every array and maintain a frequency map using a hash table. The key insight is that a value belongs in the final intersection only if its count equals the number of arrays. After counting, iterate through the map and collect numbers whose frequency equals nums.length. Since the output must be sorted, apply a final sort step on the result list.
Hash table lookups and updates run in constant time on average, making the overall counting phase linear with respect to the total number of elements across all arrays. This approach works well for the general case and handles duplicate values naturally because the counting logic focuses on array presence rather than position.
Relevant concepts: hash table, counting, and array.
Approach 2: Set Intersection (O(N) time, O(U) space)
Another clean strategy uses set intersections. Convert the first array into a set, then iteratively intersect it with sets created from each remaining array. Each intersection keeps only elements that exist in both sets. After processing all arrays, the resulting set contains values common to every array.
This method works because set intersection removes any element missing from even one array. Most languages provide optimized set operations that run in roughly linear time relative to the number of elements involved. Once the final set is computed, convert it into a list and sort it to satisfy the problem's ordering requirement.
This approach is often shorter to implement and easier to reason about compared with manual counting. It relies on standard hash table backed sets and simple intersection operations. Sorting is still required at the end, so the final step uses typical sorting algorithms.
Recommended for interviews: Interviewers typically expect the hash map counting solution. It demonstrates understanding of frequency tracking and how to aggregate information across multiple arrays. The set intersection approach is equally valid and often more concise, but explaining the counting logic clearly shows strong command of hash-based techniques used in many array problems.
Approach 1: Using Hash Maps
This approach involves using a hash map to count the occurrences of each integer across all sub-arrays. By iterating through each integer array, we populate the hash map with the count data. At the end, any integer that appears the same number of times as there are sub-arrays is included in the result, as it indicates the integer is present in each array.
def intersection(nums):
from collections import defaultdict
count_map = defaultdict(int)
for array in nums:
seen = set()
for num in array:
if num not in seen:
count_map[num] += 1
seen.add(num)
result = sorted([num for num, count in count_map.items() if count == len(nums)])
return result
# Example usage
nums = [[3, 1, 2, 4, 5], [1, 2, 3, 4], [3, 4, 5, 6]]
print(intersection(nums))import java.util.*;
public class ArrayIntersection {
public static List<Integer> intersection(List<List<Integer>> nums) {
Map<Integer, Integer> countMap = new HashMap<>();
for (List<Integer> array : nums) {
Set<Integer> seen = new HashSet<>();
for (int num : array) {
if (!seen.contains(num)) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
seen.add(num);
}
}
}
List<Integer> result = new ArrayList<>();
int totalArrays = nums.size();
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
if (entry.getValue() == totalArrays) {
result.add(entry.getKey());
}
}
Collections.sort(result);
return result;
}
public static void main(String[] args) {
List<List<Integer>> nums = new ArrayList<>();
nums.add(Arrays.asList(3, 1, 2, 4, 5));
nums.add(Arrays.asList(1, 2, 3, 4));
nums.add(Arrays.asList(3, 4, 5, 6));
List<Integer> intersection = intersection(nums);
System.out.println(intersection);
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
std::vector<int> intersection(std::vector<std::vector<int>> &nums) {
std::unordered_map<int, int> freqCount;
int totalArrays = nums.size();
for (const auto &array : nums) {
std::unordered_set<int> seen;
for (int num : array) {
if (seen.find(num) == seen.end()) {
freqCount[num]++;
seen.insert(num);
}
}
}
std::vector<int> result;
for (const auto &[num, count] : freqCount) {
if (count == totalArrays) {
result.push_back(num);
}
}
std::sort(result.begin(), result.end());
return result;
}
int main() {
std::vector<std::vector<int>> nums = {{3, 1, 2, 4, 5}, {1, 2, 3, 4}, {3, 4, 5, 6}};
auto result = intersection(nums);
std::cout << "[";
for (size_t i = 0; i < result.size(); ++i) {
std::cout << result[i] << (i + 1 < result.size() ? ", " : "");
}
std::cout << "]";
return 0;
}function intersection(nums) {
const countMap = {};
for (const list of nums) {
const seen = new Set();
for (const num of list) {
if (!seen.has(num)) {
countMap[num] = (countMap[num] || 0) + 1;
seen.add(num);
}
}
}
return Object.entries(countMap)
.filter(([key, value]) => value === nums.length)
.map(([key]) => parseInt(key))
.sort((a, b) => a - b);
}
// Example usage
const nums = [[3, 1, 2, 4, 5], [1, 2, 3, 4], [3, 4, 5, 6]];
console.log(intersection(nums));#include <stdio.h>
#include <stdbool.h>
void findIntersection(int* nums[], int numsSize, int numsColSize[], int **result, int *resultSize) {
int count[1001] = {0};
int distinctNums = 0;
for (int i = 0; i < numsSize; ++i) {
bool unique[1001] = {false};
for (int j = 0; j < numsColSize[i]; ++j) {
int num = nums[i][j];
if (!unique[num]) {
if (count[num] == i) {
++count[num];
}
unique[num] = true;
}
}
}
*resultSize = 0;
for (int i = 1; i <= 1000; ++i) {
if (count[i] == numsSize) {
(*result)[(*resultSize)++] = i;
}
}
}
int main() {
// Example input
int a1[] = {3, 1, 2, 4, 5};
int a2[] = {1, 2, 3, 4};
int a3[] = {3, 4, 5, 6};
int* nums[] = {a1, a2, a3};
int numsColSize[] = {5, 4, 4};
int result[1000];
int resultSize;
findIntersection(nums, 3, numsColSize, &result, &resultSize);
printf("[");
for (int i = 0; i < resultSize; ++i) {
printf("%d%c", result[i], i == resultSize - 1 ? ']' : ',');
}
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
public class ArrayIntersection {
public static List<int> Intersection(List<List<int>> nums) {
var dict = new Dictionary<int, int>();
foreach (var list in nums) {
var seen = new HashSet<int>();
foreach (var num in list) {
if (!seen.Contains(num)) {
seen.Add(num);
if (!dict.ContainsKey(num)) {
dict[num] = 0;
}
dict[num]++;
}
}
}
var result = from entry in dict
where entry.Value == nums.Count
select entry.Key;
return result.OrderBy(x => x).ToList();
}
public static void Main() {
var nums = new List<List<int>>
{
new List<int> {3, 1, 2, 4, 5},
new List<int> {1, 2, 3, 4},
new List<int> {3, 4, 5, 6}
};
var result = Intersection(nums);
Console.WriteLine("[" + string.Join(", ", result) + "]");
}
}The Python solution leverages defaultdict for counting and set to track unique integers within each array. After counting the occurrences, a list comprehension finds integers appearing in all arrays, which is finally sorted before returning.
Time Complexity: O(n log n). Space Complexity: O(n) due to additional storage in maps.
Approach 2: Using Set Intersections
Sets provide built-in operations for finding intersections, so this approach initializes the set of result with elements from the first array, and iteratively intersects it with subsequent sets. This efficiently prunes elements not common to all arrays and provides automatic sorting for final output.
def intersection(nums):
result_set = set(nums[0])
for array in nums[1:]:
result_set &= set(array)
return sorted(result_set)
# Example usage
nums = [[3, 1, 2, 4, 5], [1, 2, 3, 4], [3, 4, 5, 6]]
print(intersection(nums))import java.util.*;
public class SetIntersection {
public static List<Integer> intersection(List<List<Integer>> nums) {
Set<Integer> result = new HashSet<>(nums.get(0));
for (int i = 1; i < nums.size(); i++) {
result.retainAll(new HashSet<>(nums.get(i)));
}
List<Integer> resultList = new ArrayList<>(result);
Collections.sort(resultList);
return resultList;
}
public static void main(String[] args) {
List<List<Integer>> nums = new ArrayList<>();
nums.add(Arrays.asList(3, 1, 2, 4, 5));
nums.add(Arrays.asList(1, 2, 3, 4));
nums.add(Arrays.asList(3, 4, 5, 6));
List<Integer> intersection = intersection(nums);
System.out.println(intersection);
}
}#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
std::vector<int> intersection(std::vector<std::vector<int>> &nums) {
std::set<int> result(nums[0].begin(), nums[0].end());
for (size_t i = 1; i < nums.size(); ++i) {
std::set<int> s(nums[i].begin(), nums[i].end());
std::set<int> temp;
std::set_intersection(result.begin(), result.end(),
s.begin(), s.end(),
std::inserter(temp, temp.begin()));
result = temp;
}
return std::vector<int>(result.begin(), result.end());
}
int main() {
std::vector<std::vector<int>> nums = {{3, 1, 2, 4, 5}, {1, 2, 3, 4}, {3, 4, 5, 6}};
auto result = intersection(nums);
std::cout << "[";
for (size_t i = 0; i < result.size(); ++i) {
std::cout << result[i] << (i + 1 < result.size() ? ", " : "");
}
std::cout << "]";
return 0;
}function intersection(nums) {
let resultSet = new Set(nums[0]);
for (let i = 1; i < nums.length; i++) {
resultSet = new Set(nums[i].filter(num => resultSet.has(num)));
}
return Array.from(resultSet).sort((a, b) => a - b);
}
// Example usage
const nums = [[3, 1, 2, 4, 5], [1, 2, 3, 4], [3, 4, 5, 6]];
console.log(intersection(nums));using System;
using System.Collections.Generic;
using System.Linq;
public class Program {
public static List<int> Intersection(List<List<int>> nums) {
HashSet<int> resultSet = new HashSet<int>(nums[0]);
for (int i = 1; i < nums.Count; i++) {
resultSet.IntersectWith(nums[i]);
}
List<int> result = resultSet.ToList();
result.Sort();
return result;
}
public static void Main() {
var nums = new List<List<int>> {
new List<int> {3, 1, 2, 4, 5},
new List<int> {1, 2, 3, 4},
new List<int> {3, 4, 5, 6}
};
var result = Intersection(nums);
Console.WriteLine("[" + string.Join(", ", result) + "]");
}
}This Python approach uses the intersection operator '&=' of sets to retain only elements appearing in all sub-arrays. The result is converted to a sorted list before being returned for an intuitive solution.
Time Complexity: O(n log n) where n is the total number of unique elements due to sorting. Space Complexity: O(n) for storing sets.
Approach 3: Counting
Traverse the array nums. For each sub-array arr, count the occurrence of each number in arr. Then traverse the count array, count the numbers that appear as many times as the length of the array nums, which are the answers.
The time complexity is O(N), and the space complexity is O(1000). Where N is the total number of numbers in the array nums.
function intersection(nums: number[][]): number[] {
const cnt = new Array(1001).fill(0);
for (const arr of nums) {
for (const x of arr) {
cnt[x]++;
}
}
const ans: number[] = [];
for (let x = 0; x < 1001; x++) {
if (cnt[x] === nums.length) {
ans.push(x);
}
}
return ans;
}func intersection(nums [][]int) (ans []int) {
cnt := [1001]int{}
for _, arr := range nums {
for _, x := range arr {
cnt[x]++
}
}
for x, v := range cnt {
if v == len(nums) {
ans = append(ans, x)
}
}
return
}class Solution {
/**
* @param Integer[][] $nums
* @return Integer[]
*/
function intersection($nums) {
$rs = [];
for ($i = 0; $i < count($nums); $i++) {
for ($j = 0; $j < count($nums[$i]); $j++) {
$hashtable[$nums[$i][$j]] += 1;
if ($hashtable[$nums[$i][$j]] === count($nums)) {
array_push($rs, $nums[$i][$j]);
}
}
}
sort($rs);
return $rs;
}
}Approach 4: Default Approach
function intersection(nums: number[][]): number[] {
const cnt = new Array(1001).fill(0);
const ans: number[] = [];
for (const arr of nums) {
for (const x of arr) {
if (++cnt[x] == nums.length) {
ans.push(x);
}
}
}
ans.sort((a, b) => a - b);
return ans;
}func intersection(nums [][]int) (ans []int) {
cnt := map[int]int{}
for _, arr := range nums {
for _, x := range arr {
cnt[x]++
if cnt[x] == len(nums) {
ans = append(ans, x)
}
}
}
sort.Ints(ans)
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Hash Maps | Time Complexity: O(n log n). Space Complexity: O(n) due to additional storage in maps. |
| Using Set Intersections | Time Complexity: O(n log n) where n is the total number of unique elements due to sorting. Space Complexity: O(n) for storing sets. |
| Counting | – |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Counting | O(N + K log K) | O(U) | General case when processing many arrays and counting element frequency |
| Set Intersection | O(N + K log K) | O(U) | Cleaner implementation when languages support fast set intersection |
Frequently asked questions
Is Intersection of Multiple Arrays easy or hard?
Intersection of Multiple Arrays is classified as an Easy problem on LeetCode. The main idea is recognizing that either frequency counting or set intersection can efficiently track elements that appear in every array.
Intersection of Multiple Arrays Python/Java solution
Python solutions commonly use dictionaries or the built-in set intersection operator. Java implementations typically use HashMap for counting or HashSet with retainAll operations. Both approaches run in linear time relative to the total input size.
How to solve Intersection of Multiple Arrays in O(n)?
Use a hash map to count occurrences across arrays. Iterate through every number and increment its count. After processing all arrays, collect numbers whose count equals the number of arrays. This makes the main computation O(N) with an additional sorting step for the final output.
What is the best approach for Intersection of Multiple Arrays?
The most common approach uses a hash map to count how many arrays contain each number. After scanning all arrays, numbers with frequency equal to the total number of arrays belong to the intersection. This runs in O(N) time for counting plus sorting of the result.
Is Intersection of Multiple Arrays asked at Google/Amazon/Meta?
Problems involving array intersection and hash map counting frequently appear in interviews at companies like Amazon, Google, and Meta. Variations include intersecting two arrays, finding common elements across multiple lists, or computing frequency-based intersections.
What data structure is used in Intersection of Multiple Arrays?
The primary data structures are hash maps for counting frequencies and hash sets for intersection operations. These structures provide average O(1) lookup and insertion, which keeps the algorithm efficient even with many elements.
What is the time complexity of Intersection of Multiple Arrays?
The counting or set-based solution processes each element once, giving O(N) time where N is the total number of elements across all arrays. The final result must be sorted, which adds O(K log K) where K is the size of the intersection.