Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1213.html
1213. Intersection of Three Sorted Arrays
Level
Easy
Description
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.
Constraints:
1 <= arr1.length, arr2.length, arr3.length <= 1000
1 <= arr1[i], arr2[i], arr3[i] <= 2000
Solution
Since all three arrays are sorted in strictly increasing order, it can be determined that if an array’s current integer is greater than another array’s current integer, then the another array’s current integer can’t be in the intersection.
Use three pointers in three arrays respectively to find the integers that appear in all three arrays. Initially, the three pointers point to the beginning of the three arrays respectively. Each time check the three integers that the three pointers point to. If a pointer points to an integer that is less than any of the other two integers, then move the pointer one step forward. Only if the three integers that three pointers point to are the same, the integer is in the intersection, and add the integer to the result list.
-
class Solution { public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) { List<Integer> intersection = new ArrayList<Integer>(); int length1 = arr1.length, length2 = arr2.length, length3 = arr3.length; int index1 = 0, index2 = 0, index3 = 0; while (index1 < length1 && index2 < length2 && index3 < length3) { int num1 = arr1[index1], num2 = arr2[index2], num3 = arr3[index3]; if (num1 == num2 && num1 == num3) { intersection.add(num1); index1++; index2++; index3++; } else { int increment1 = 0, increment2 = 0, increment3 = 0; if (num1 < num2 || num1 < num3) increment1 = 1; if (num2 < num1 || num2 < num3) increment2 = 1; if (num3 < num1 || num3 < num2) increment3 = 1; index1 += increment1; index2 += increment2; index3 += increment3; } } return intersection; } }
-
// OJ: https://leetcode.com/problems/intersection-of-three-sorted-arrays/ // Time: O(A + B + C) // Space: O(1) class Solution { public: vector<int> arraysIntersection(vector<int>& A, vector<int>& B, vector<int>& C) { int i = 0, j = 0, k = 0, R = A.size(), S = B.size(), T = C.size(); vector<int> ans; while (i < R && j < S && k < T) { int a = A[i], b = B[j], c = C[k]; if (a == b && b == c) { ans.push_back(a); ++i, ++j, ++k; } else { int mx = max({ a, b, c }); if (a < mx) ++i; if (b < mx) ++j; if (c < mx) ++k; } } return ans; } };
-
class Solution: def arraysIntersection( self, arr1: List[int], arr2: List[int], arr3: List[int] ) -> List[int]: def find(arr, val): left, right = 0, len(arr) - 1 while left < right: mid = (left + right) >> 1 if arr[mid] >= val: right = mid else: left = mid + 1 return arr[left] == val res = [] for num in arr1: if find(arr2, num) and find(arr3, num): res.append(num) return res
-
func arraysIntersection(arr1 []int, arr2 []int, arr3 []int) (ans []int) { cnt := [2001]int{} for _, x := range arr1 { cnt[x]++ } for _, x := range arr2 { cnt[x]++ } for _, x := range arr3 { cnt[x]++ if cnt[x] == 3 { ans = append(ans, x) } } return }
-
class Solution { /** * @param Integer[] $arr1 * @param Integer[] $arr2 * @param Integer[] $arr3 * @return Integer[] */ function arraysIntersection($arr1, $arr2, $arr3) { $rs = []; $arr = array_merge($arr1, $arr2, $arr3); for ($i = 0; $i < count($arr); $i++) { $hashtable[$arr[$i]] += 1; if ($hashtable[$arr[$i]] === 3) array_push($rs, $arr[$i]); } return $rs; } }