1213. Intersection of Three Sorted Arrays

Problem Statement

link: LeetCode.cn LeetCode 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:

Input: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8] Output: [1,5]

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

Solution Approach

The solution finds the intersection of three sorted arrays by either using set operations to identify common elements or by counting the occurrences of each element and returning those that appear in all three arrays.

Algorithm

1. Use Set Intersection: Convert the three arrays into sets and find the intersection of these sets to identify common elements across all arrays.
2. Count Element Frequencies: Concatenate the three arrays and use a dictionary to count the frequency of each element, identifying those that appear exactly three times.
3. Sort and Return: After identifying the common elements, sort the resulting list to ensure the final output is in ascending order.

Implement

    class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        return sorted(list(set(arr1) & set(arr2) & set(arr3)))

class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        ref = arr1 + arr2 + arr3
        dic = Counter(ref)
        alist = sorted(dic.items(),key=lambda x:x[1])
        res = list()
        for i in range(len(alist)-1,-1,-1):
            if alist[i][1] == 3:
                res.append(alist[i][0])
            else:
                break
        return sorted(res)

    
    

Twitter  facebook  Email