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 <= 10001 <= arr1[i], arr2[i], arr3[i] <= 2000Problem 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.
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.
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.
| Approach | Complexity |
|---|---|
| Counting | — |
| Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting with Hash Table | O(n1 + n2 + n3) | O(n1 + n2) | Best when linear scanning is acceptable and extra memory is not a concern |
| Binary Search | O(n1 log n2 + n1 log n3) | O(1) | Useful when arrays are sorted and you want constant extra space |
LeetCode 1213: Intersection of Three Sorted Arrays - Interview Prep Ep 5 • Fisher Coder • 2,873 views views
Watch 9 more video solutions →Practice Intersection of Three Sorted Arrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor