Skip to content

1213. Intersection of Three Sorted Arrays πŸ”’

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.

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

Solutions

Solution 1: Counting

Thinking

The three arrays are sorted, length at most \(1000\), and values lie in \([1,2000]\). Counting all three, a value with count \(3\) is common; elements are unique inside each array, so one array cannot inflate the count. Emitting in \(arr1\) order keeps the result sorted.

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.

1
2
3
4
5
6
class Solution:
    def arraysIntersection(
        self, arr1: List[int], arr2: List[int], arr3: List[int]
    ) -> List[int]:
        cnt = Counter(arr1 + arr2 + arr3)
        return [x for x in arr1 if cnt[x] == 3]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
        List<Integer> ans = new ArrayList<>();
        int[] cnt = new int[2001];
        for (int x : arr1) {
            ++cnt[x];
        }
        for (int x : arr2) {
            ++cnt[x];
        }
        for (int x : arr3) {
            if (++cnt[x] == 3) {
                ans.add(x);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> ans;
        int cnt[2001]{};
        for (int x : arr1) {
            ++cnt[x];
        }
        for (int x : arr2) {
            ++cnt[x];
        }
        for (int x : arr3) {
            if (++cnt[x] == 3) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
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;
    }
}

Thinking

Counting needs an array proportional to the value range. The arrays are already sorted, so we binary-search each \(arr1\) value in \(arr2\) and \(arr3\). Extra space becomes constant; time becomes \(O(n\log n)\).

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def arraysIntersection(
        self, arr1: List[int], arr2: List[int], arr3: List[int]
    ) -> List[int]:
        ans = []
        for x in arr1:
            i = bisect_left(arr2, x)
            j = bisect_left(arr3, x)
            if i < len(arr2) and j < len(arr3) and arr2[i] == x and arr3[j] == x:
                ans.append(x)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
        List<Integer> ans = new ArrayList<>();
        for (int x : arr1) {
            int i = Arrays.binarySearch(arr2, x);
            int j = Arrays.binarySearch(arr3, x);
            if (i >= 0 && j >= 0) {
                ans.add(x);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
        vector<int> ans;
        for (int x : arr1) {
            auto i = lower_bound(arr2.begin(), arr2.end(), x);
            auto j = lower_bound(arr3.begin(), arr3.end(), x);
            if (*i == x && *j == x) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func arraysIntersection(arr1 []int, arr2 []int, arr3 []int) (ans []int) {
    for _, x := range arr1 {
        i := sort.SearchInts(arr2, x)
        j := sort.SearchInts(arr3, x)
        if i < len(arr2) && j < len(arr3) && arr2[i] == x && arr3[j] == x {
            ans = append(ans, x)
        }
    }
    return
}

Comments