1213. Intersection of Three Sorted Arrays

This problem asks to find the intersection of three sorted arrays, meaning the numbers that appear in all three arrays. The solution can be approached in a couple of ways: using counting or using binary search.

Solution 1: Counting

This approach uses a frequency count to efficiently determine which numbers appear in all three arrays.

Algorithm:

1. Create a frequency counter: Initialize a hash map (or array if the range of numbers is known and relatively small, as it is in this problem) to store the frequency of each number across all three input arrays.
2. Count occurrences: Iterate through each of the three input arrays (arr1, arr2, arr3), incrementing the count for each number encountered in the frequency counter.
3. Identify common numbers: Iterate through one of the arrays (it doesn't matter which). If the frequency of a number is equal to 3 (meaning it's present in all three arrays), add it to the result list.
4. Return the result: Return the result list, which contains the numbers that appear in all three arrays.

Time Complexity: O(N), where N is the total number of elements across all three arrays. This is because we iterate through each array once.

Space Complexity: O(M), where M is the range of numbers (2001 in this specific problem). This is the space used by the frequency counter. If we used a hash map, the space complexity would be O(K) where K is the number of unique elements.

Code (Python):

from collections import Counter
 
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]
 

Code (Java):

import java.util.*;
 
class Solution {
    public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
        List<Integer> ans = new ArrayList<>();
        int[] cnt = new int[2001]; // Since numbers are in range [1, 2000]
        for (int x : arr1) cnt[x]++;
        for (int x : arr2) cnt[x]++;
        for (int x : arr3) {
            cnt[x]++;
            if (cnt[x] == 3) ans.add(x);
        }
        return ans;
    }
}

Solution 2: Binary Search

This approach uses binary search to efficiently check if a number exists in the other two arrays.

Algorithm:

1. Iterate through the first array: Iterate through each number in arr1.
2. Binary Search: For each number, perform a binary search in arr2 and arr3 to check if it exists.
3. Check for presence: If the number is found in both arr2 and arr3, add it to the result list.
4. Return the result: Return the result list.

Time Complexity: O(N log N), where N is the maximum length among the three arrays. This is because we iterate through one array (O(N)) and perform binary search on the others (O(log N) each).

Space Complexity: O(1), as we are using only a constant amount of extra space.

Code (Python):

import bisect
 
class Solution:
    def arraysIntersection(self, arr1: list[int], arr2: list[int], arr3: list[int]) -> list[int]:
        ans = []
        for x in arr1:
            if bisect.bisect_left(arr2, x) < len(arr2) and arr2[bisect.bisect_left(arr2, x)] == x and \
               bisect.bisect_left(arr3, x) < len(arr3) and arr3[bisect.bisect_left(arr3, x)] == x:
                ans.append(x)
        return ans

Code (Java):

import java.util.*;
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;
    }
}

The counting approach is generally preferred for this problem due to its linear time complexity, making it more efficient for larger input arrays. The binary search approach is a viable alternative, but its logarithmic time complexity improvement doesn't outweigh the constant factor overhead for reasonably sized inputs.