Problem

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.

Examples

Example 1:

1
2
3

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

Method 1 - 3 Pointer Technique

Here is the approach:

  • Use three pointers, one for each array, initialized to the beginning of the arrays.
  • Compare the elements pointed to by the three pointers.
  • If all three elements are equal, add the element to the result and move all three pointers forward.
  • If the elements are not equal, move the pointer pointing to the smallest element forward.
  • Continue until at least one of the pointers reaches the end of its respective array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Solution {
    public List<Integer> findCommonElements(int[] arr1, int[] arr2, int[] arr3) {
        int i = 0, j = 0, k = 0;
        List<Integer> commonElements = new ArrayList<>();

        while (i < arr1.length && j < arr2.length && k < arr3.length) {
            // If all three pointers have the same value, add it to the result
            if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {
                commonElements.add(arr1[i]);
                i++;
                j++;
                k++;
            // Move the pointer in the smallest value
            } else if (arr1[i] < arr2[j]) {
                i++;
            } else if (arr2[j] < arr3[k]) {
                j++;
            } else {
                k++;
            }
        }

        return commonElements;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def findCommonElements(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        i, j, k = 0, 0, 0
        common_elements = []

        while i < len(arr1) and j < len(arr2) and k < len(arr3):
            # If all three pointers have the same value, add it to the result
            if arr1[i] == arr2[j] == arr3[k]:
                common_elements.append(arr1[i])
                i += 1
                j += 1
                k += 1
            # Move the pointer in the smallest value
            elif arr1[i] < arr2[j]:
                i += 1
            elif arr2[j] < arr3[k]:
                j += 1
            else:
                k += 1

        return common_elements

Complexity

  • ⏰ Time complexity: O(n1 + n2 + n3), where n1, n2, and n3 are the lengths of the three arrays, because we traverse each array at most once.
  • 🧺 Space complexity: O(min(n1, n2, n3)), for storing the common elements in the result list.

Method 2 - Using Frequency array

We can use count array to count all the numbers, and when the frequency becomes 3, we have found a number. WE can create a frequency array of size 2001, as in constraint we have 2000 elements.

Code

 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
20
21
22
23
24
25

class Solution:
    def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
        count = {}
        result = []

        # Count frequency of each element in arr1
        for x in arr1:
            if x in count:
                count[x] += 1
            else:
                count[x] = 1
        
        # Count frequency of each element in arr2
        for x in arr2:
            if x in count:
                count[x] += 1
            else:
                count[x] = 1

        # Check elements in arr3 and if their count reaches 3, add to result
        for x in arr3:
            if x in count and count[x] == 2:
                result.append(x)

        return result

Complexity

  • ⏰ Time complexity: O(n1 + n2 + n3)
  • 🧺 Space complexity: O(min(n1, n2, n3))