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.

• Java
• C++
• Python
• Go
• Php

• 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;
      }
  }
  

All Problems

All Solutions