Problem

Given three arrays that are sorted in increasing order, we are to find the integers that appear in all three of the sorted arrays.

For instance, given the sorted arrays arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8], we can see that 1 and 5 appear in all the arrays.

Approach

The approach is simple. Since each array is sorted in ascending order, we just need to iterate through each of the arrays concurrently and check if an integer appears in all the sorted arrays. To do this, we initialize three pointers i, j, and k to the beginning of each array.

Then, for each iteration, we check if the integer at the current pointer appears in all the arrays. If it does, we add it to a result array ans and move all pointers one step forward. If it doesn't, we move the pointer corresponding to the smallest element one step forward and repeat the process until we reach the end of any of the arrays.

Solution

Python

1
2python
3class Solution:
4  def arraysIntersection(self, arr1, arr2, arr3):
5    ans = []
6    i = 0
7    j = 0
8    k = 0
9
10    while (i < len(arr1) and j < len(arr2) and k < len(arr3)):
11      mini = min(arr1[i], arr2[j], arr3[k])
12      if arr1[i] == mini and arr2[j] == mini and arr3[k] == mini:
13        ans.append(mini)
14        i += 1
15        j += 1
16        k += 1
17      elif arr1[i] == mini:
18        i += 1
19      elif arr2[j] == mini:
20        j += 1
21      else:
22        k += 1
23
24    return ans;

Java

1
2java
3class Solution {
4    public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
5        List<Integer> ans = new ArrayList<>();
6        int i = 0;
7        int j = 0;
8        int k = 0;
9
10        while (i < arr1.length && j < arr2.length && k < arr3.length) {
11            int mini = Math.min(Math.min(arr1[i], arr2[j]), arr3[k]);
12            if (arr1[i] == mini && arr2[j] == mini && arr3[k] == mini) {
13                ans.add(mini);
14                i++;
15                j++;
16                k++;
17            } else if (arr1[i] == mini) {
18              i++;
19            } else if (arr2[j] == mini) {
20              j++;
21            } else {
22              k++;
23            }
24        }
25
26        return ans;
27    }
28}

JavaScript

1
2javascript
3class Solution {
4  arraysIntersection(arr1, arr2, arr3) {
5    let ans = [];
6    let i = 0;
7    let j = 0;
8    let k = 0;
9
10    while (i < arr1.length && j < arr2.length && k < arr3.length) {
11      let mini = Math.min(Math.min(arr1[i], arr2[j]), arr3[k]);
12      if (arr1[i] == mini && arr2[j] == mini && arr3[k] == mini){
13        ans.push(mini);
14        i++;
15        j++;
16        k++;
17      } else if (arr1[i] == mini) {
18        i++;
19      } else if (arr2[j] == mini) {
20        j++;
21      } else {
22        k++;
23      }
24    }
25
26    return ans;
27  }
28}

C++

1
2cpp
3class Solution {
4public:
5    vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
6        vector<int> ans;
7        int i = 0;
8        int j = 0;
9        int k = 0;
10
11        while (i < arr1.size() && j < arr2.size() && k < arr3.size()) {
12            int mini = min({arr1[i], arr2[j], arr3[k]});
13            if (arr1[i] == mini && arr2[j] == mini && arr3[k] == mini) {
14                ans.push_back(mini);
15                ++i;
16                ++j;
17                ++k;
18            } else if (arr1[i] == mini) {
19                ++i;
20            } else if (arr2[j] == mini) {
21                ++j;
22            } else {
23                ++k;
24            }
25        }
26
27        return ans;
28    }
29};

C#

1
2csharp
3public class Solution {
4    public IList<int> ArraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
5        List<int> ans = new List<int>();
6        int i = 0;
7        int j = 0;
8        int k = 0;
9
10        while (i < arr1.Length && j < arr2.Length && k < arr3.Length) {
11            int mini = Math.Min(Math.Min(arr1[i], arr2[j]), arr3[k]);
12            if (arr1[i] == mini && arr2[j] == mini && arr3[k] == mini) {
13                ans.Add(mini);
14                i++;
15                j++;
16                k++;
17            } else if (arr1[i] == mini) {
18                i++;
19            } else if (arr2[j] == mini) {
20                j++;
21            } else {
22                k++;
23            }
24        }
25
26        return ans;
27    }
28}

These solutions all take advantage of the fact that the arrays are sorted. By moving the pointers through each array only when their current value is the smallest, we ensure that we do not miss any integers that are common to all three arrays, while also avoiding unnecessary comparisons. This allows for a computation complexity of O(n) where n is the length of the arrays.

It would be worth noting that while this approach has an optimal time complexity, it might be inefficient if the three arrays were of vastly different sizes. If one array is significantly larger, we would still be required to iterate through that entire array, even though we know that there can be no more common elements once we reach the end of the smallest array.

In such case:

• We can first start by checking the size of all input arrays and identifying the smallest.
• We start iterating on the smallest array while checking if its elements exist in the other two arrays.
• As per the language being used, there are various methods which can help you in searching an element in an array such as binary search, in-build functions as contains in Java, in keyword in Python and so on.

It is always essential to comprehend the provided data and adjust your approach accordingly for better efficiency and optimised solutions. As the coding maxim goes: Always code as if the person who ends up maintaining your code is a violent psychopath who knows where you live.