Is Intersection of Three Sorted Arrays easy or hard?

Intersection of Three Sorted Arrays is considered an Easy problem on most coding platforms. The logic mainly involves array iteration, hash table lookups, or binary search on sorted data, making it a good practice problem for beginners.

Intersection of Three Sorted Arrays Python/Java solution

In Python or Java, the typical solution uses a hash map (dictionary or HashMap) to track counts from the first two arrays and then validates elements from the third array. Another implementation uses binary search on the other arrays for each candidate element.

How to solve Intersection of Three Sorted Arrays in O(n)?

Use a hash table to count how many arrays contain each value. Insert elements from the first two arrays into a map and increase their counts. While scanning the third array, check whether the count equals two; if it does, the element exists in all three arrays. This achieves linear time across all inputs.

What is the best approach for Intersection of Three Sorted Arrays?

A linear counting approach using a hash table is the most straightforward solution. Scan the first two arrays and store element frequencies, then verify elements from the third array. This runs in O(n1 + n2 + n3) time with O(n) additional space and is easy to implement during interviews.

Is Intersection of Three Sorted Arrays asked at Google/Amazon/Meta?

Array intersection and frequency counting problems appear frequently in interviews at large tech companies such as Amazon, Google, and Meta. Variations include intersections of multiple arrays, set intersections, and deduplicating results using hash tables or two-pointer techniques.

What data structure is used in Intersection of Three Sorted Arrays?

The most common data structure is a hash table used for frequency counting across arrays. Because the arrays are sorted, binary search can also be used to check membership efficiently without additional storage.

What is the time complexity of Intersection of Three Sorted Arrays?

The common optimal approach using counting runs in O(n1 + n2 + n3) time because each array is scanned once. A binary search alternative runs in O(n1 log n2 + n1 log n3) time when searching elements from one array inside the other two.

Description Hints 2 Solution Video 7:00

1213. Intersection of Three Sorted Arrays

Easy80.2% acceptance2 companiesPremium elsewhere, free here

Given three integer arrays arr1, arr2 and arr3 sorted in strictly increasing order, return a sorted array of only the integers that appeared in all three arrays.

Example 1:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
Output: [1,5]
Explanation: Only 1 and 5 appeared in the three arrays.

Example 2:

Input: arr1 = [197,418,523,876,1356], arr2 = [501,880,1593,1710,1870], arr3 = [521,682,1337,1395,1764]
Output: []

Constraints:

1 <= arr1.length, arr2.length, arr3.length <= 1000
1 <= arr1[i], arr2[i], arr3[i] <= 2000

Asked at 2 companies

Meta Apple

Topics

Hints open one at a time

Hint 1

Count the frequency of all elements in the three arrays.

Hint 2

The elements that appeared in all the arrays would have a frequency of 3.

7:00

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution