Skip to main content
Talentd

Intersection of Multiple Arrays - Solution & Explanation

EasyArrayHash TableSortingCounting17 min readAsked at: Meta, Uber
Practice this problem

Problem Statement

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 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 <= 1000
  • 1 <= sum(nums[i].length) <= 1000
  • 1 <= 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.

The solution utilizes an array of size 1001 to count occurrences of each number across sub-arrays, tracking each number's presence uniquely within a sub-array to prevent counting a number multiple times per array. The result is formed by gathering numbers that appear in all sub-arrays.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the total number of elements across all arrays. Space Complexity: O(1), since the auxiliary space used (count array) is fixed.

Try this approach in the editor →

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.

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.

Code

PythonC++JavaJavaScriptC#

Python

C++

Java

JavaScript

C#

Complexity

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.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptPHP

Python

Java

C++

Go

TypeScript

PHP

Try this approach in the editor →

Approach 4: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using Hash Maps

Time Complexity: O(n), where n is the total number of elements across all arrays. Space Complexity: O(1), since the auxiliary space used (count array) is fixed.

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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map CountingO(N + K log K)O(U)General case when processing many arrays and counting element frequency
Set IntersectionO(N + K log K)O(U)Cleaner implementation when languages support fast set intersection

Video Solution

Intersection of Multiple Arrays | Leetcode 2248 | Strings | Contest 290 🔥🔥 • Coding Decoded • 2,477 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Intersection of Multiple Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Smallest Common Element in All Rows

Next

Find the Difference of Two Arrays