Skip to main content
Talentd

Intersection of Three Sorted Arrays - Solution & Explanation

EasyPremiumFree on FleetCodeArrayHash TableBinary SearchCounting8 min readAsked at: Apple, Meta
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You get three sorted integer arrays. The task is to return all values that appear in all three arrays. Since the arrays are sorted and contain integers, you can exploit ordering or use frequency counting to detect values present in every array.

Approach 1: Counting with Hash Table (O(n1 + n2 + n3) time, O(n1 + n2) space)

This approach tracks how many arrays contain each value. Iterate through the first two arrays and record counts in a hash map or frequency table. Each key represents a number and the value represents how many arrays have seen it so far. When scanning the third array, check whether the number already appeared in both earlier arrays (count equals 2). If so, add it to the result.

The key insight is that the intersection condition is simply a frequency check across arrays. A hash map provides constant-time lookup, so membership tests stay efficient. This works even if the arrays were not sorted, making it a flexible solution for general intersection problems. It relies on concepts from hash tables, counting, and basic array iteration.

Approach 2: Binary Search (O(n1 log n2 + n1 log n3) time, O(1) space)

Because the arrays are sorted, you can search efficiently instead of storing counts. Iterate through one array (usually the smallest). For each element x, run binary search on the other two arrays to check whether x exists there. If both searches succeed, append the element to the result.

The key operation here is binary search, which reduces lookup time from linear to logarithmic. Instead of scanning entire arrays, you repeatedly split the search interval in half until the element is found or ruled out. This eliminates extra memory usage while keeping lookups efficient. The approach is based on classic binary search techniques applied across multiple sorted arrays.

Recommended for interviews: The counting solution is typically the easiest to implement and achieves linear time, which already meets optimal performance for scanning all arrays. Interviewers like to see that you recognize the intersection condition and translate it into a frequency check using a hash map. The binary search approach demonstrates that you noticed the arrays are sorted and can leverage that property to reduce lookups without extra memory.

Approach 1: Counting

Traverse the three arrays, count the occurrence of each number, then traverse any one of the arrays. If the count of a number is 3, add it to the result array.

The time complexity is O(n), and the space complexity is O(m). Here, n and m are the length of the array and the range of numbers in the array, respectively.

Code

PythonJavaC++GoPHP

Python

Java

C++

Go

PHP

Try this approach in the editor →

Approach 2: Binary Search

Traverse the first array. For each number, use binary search to find this number in the second and third arrays. If found in both, add this number to the result array.

The time complexity is O(n times log n), and the space complexity is O(1). Here, n is the length of the array.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Counting—
Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counting with Hash TableO(n1 + n2 + n3)O(n1 + n2)Best when linear scanning is acceptable and extra memory is not a concern
Binary SearchO(n1 log n2 + n1 log n3)O(1)Useful when arrays are sorted and you want constant extra space

Video Solution

LeetCode 1213: Intersection of Three Sorted Arrays - Interview Prep Ep 5 • Fisher Coder • 2,887 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Intersection of Multiple Arrays

Next

Intersection of Two Arrays