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] <= 2000Traverse 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.
Java
C++
Go
PHP
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.
Java
C++
Go
| Approach | Complexity |
|---|---|
| Counting | — |
| Binary Search | — |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,166 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