Find common elements in three sorted arrays

Given three sorted arrays in non-decreasing order, print all common elements in non-decreasing order across these arrays. If there are no such elements return an empty array. In this case, the output will be -1.

Note: In case of duplicate common elements, print only once.

Examples: 

Input: arr1[] = [1, 5, 10, 20, 30], arr2[] = [5, 13, 15, 20], arr3[] = [5, 20] 
Output: 5 20
Explanation: 5 and 20 are common in all the arrays.

Input: arr1[] = [2, 5, 10, 30], arr2[] = [5, 20, 34], arr3[] = [5, 13, 19]
Output: 5
Explanation: 5 is common in all the arrays.

[Naive Approach] Using Tree Map (Or Self Balancing BST) - O((n1 + n2 + n3)*log n1) Time and O(n1) Space

The basic idea is to use Tree Map for storing the common elements in three sorted arrays. This can be implemented by:

• Iterate over the first array and for each element mark its value = 1 in a self balancing BST.
• Now, iterate over the second array and for each element in the second array, mark value = 2 of only those elements which already had the value = 1 in the map. This will ensure that all the common elements among the first two arrays have value = 2 in hash table.
• Finally, iterate over the third array and for each element in the third array, mark value = 3 of only those elements which already had value = 2 in the Tree Map (or Self Balancing BST)

Important Points

• If sorted order is not required, then we can use Hashing instead of Self Balancing BST to do the work in linear time.
• In languages like Python, C# and JavaScript, there is not built in implementation of Self Balancing BST, so we use a Dictionary or Hash Table and finally do sorting.

#include <bits/stdc++.h> using namespace std; vector<int> commonElements(vector<int> &arr1, vector<int> &arr2, vector<int> &arr3) {  // hash table to mark the common elements  map<int, int> mp;  // Mark all the elements in the first Array with value=1  for (int ele : arr1)  {  mp[ele] = 1;  }  // Mark all the elements which are common in first and  // second Array with value = 2  for (int ele : arr2)  {  if (mp.find(ele) != mp.end() && mp[ele] == 1)  mp[ele] = 2;  }  // Mark all the elements which are common in first,  // second and third Array with value = 3  for (int ele : arr3)  {  if (mp.find(ele) != mp.end() && mp[ele] == 2)  mp[ele] = 3;  }  // Store all the common elements  vector<int> commonElements;  for (auto ele : mp)  {  if (ele.second == 3)  commonElements.push_back(ele.first);  }  // Return the common elements which are common in all  // the three sorted Arrays  return commonElements; } int main() {  // Sample Input  vector<int> arr1 = {1, 5, 10, 20, 30};  vector<int> arr2 = {5, 13, 15, 20};  vector<int> arr3 = {5, 20};  vector<int> common = commonElements(arr1, arr2, arr3);  if (common.size() == 0)  cout << -1;  for (int i = 0; i < common.size(); i++)  {  cout << common[i] << " ";  }  return 0; } 

import java.util.*; public class GfG {  // Function to find common elements in three arrays  public static ArrayList<Integer>  commonElements(ArrayList<Integer> arr1,  ArrayList<Integer> arr2,  ArrayList<Integer> arr3)  {  // TreeMap to mark the common elements  TreeMap<Integer, Integer> map = new TreeMap<>();  // Mark all the elements in the first array with  // value=1  for (int ele : arr1) {  map.put(ele, 1);  }  // Mark all the elements which are common in first  // and second array with value = 2  for (int ele : arr2) {  if (map.containsKey(ele) && map.get(ele) == 1)  map.put(ele, 2);  }  // Mark all the elements which are common in first,  // second, and third array with value = 3  for (int ele : arr3) {  if (map.containsKey(ele) && map.get(ele) == 2)  map.put(ele, 3);  }  // Store all the common elements  ArrayList<Integer> commonElements  = new ArrayList<>();  for (int ele : map.keySet()) {  if (map.get(ele) == 3)  commonElements.add(ele);  }  // Return the common elements which are common in  // all the three arrays  return commonElements;  }  public static void main(String[] args)  {  // Sample Input  ArrayList<Integer> arr1  = new ArrayList<>(List.of(1, 5, 10, 20, 30));  ArrayList<Integer> arr2  = new ArrayList<>(List.of(5, 13, 15, 20));  ArrayList<Integer> arr3  = new ArrayList<>(List.of(5, 20));  // Function call and storing result  ArrayList<Integer> common  = commonElements(arr1, arr2, arr3);  if (common.size() == 0)  System.out.print(-1);  for (int i = 0; i < common.size(); i++)  System.out.print(common.get(i) + " ");  } } 

def commonElements(arr1, arr2, arr3): # Hashing using dictionaries count = {} # Count occurrences in arr1 for ele in arr1: count[ele] = 1 # Increment counts for elements in arr2 for ele in arr2: if count.get(ele) == 1: count[ele] = 2 # Increment counts for elements in arr3 for ele in arr3: if count.get(ele) == 2: count[ele] = 3 # Extract common elements in sorted order return sorted([ele for ele in count if count[ele] == 3]) # Sample Input arr1 = [1, 5, 10, 20, 30] arr2 = [5, 13, 15, 20] arr3 = [5, 20] # Function call common = commonElements(arr1, arr2, arr3) if len(common) == 0: print(-1) # Print the result print(*common) 

// C# Code to find common elements in three sorted arrays using System; using System.Collections.Generic; public class GfG {  // Function to find common elements in three arrays.  static List<int> CommonElements(List<int> arr1,  List<int> arr2,  List<int> arr3)  {  // Dictionary to mark the common elements  Dictionary<int, int> mp  = new Dictionary<int, int>();  // Mark all the elements in the first array with  // value=1  foreach(int ele in arr1) { mp[ele] = 1; }  // Mark all the elements which are common in first  // and second array with value = 2  foreach(int ele in arr2)  {  if (mp.ContainsKey(ele) && mp[ele] == 1)  mp[ele] = 2;  }  // Mark all the elements which are common in first,  // second and third array with value = 3  foreach(int ele in arr3)  {  if (mp.ContainsKey(ele) && mp[ele] == 2)  mp[ele] = 3;  }  // Store all the common elements  List<int> commonElements = new List<int>();  foreach(var ele in mp)  {  if (ele.Value == 3)  commonElements.Add(ele.Key);  }  // Return the common elements which are common in  // all the three sorted arrays  commonElements.Sort();  return commonElements;  }  public static void Main(string[] args)  {  // Sample Input  List<int> arr1 = new List<int>{ 1, 5, 10, 20, 30 };  List<int> arr2 = new List<int>{ 5, 13, 15, 20 };  List<int> arr3 = new List<int>{ 5, 20 };  List<int> common = CommonElements(arr1, arr2, arr3);  if (common.Count == 0)  Console.Write(-1);  foreach(int num in common)  {  Console.Write(num + " ");  }  } } 

function commonElements(arr1, arr2, arr3) {  // Map to mark the common elements  let mp = new Map();  // Mark all the elements in the first array with value=1  arr1.forEach(ele => { mp.set(ele, 1); });  // Mark all the elements which are common in first and  // second array with value = 2  arr2.forEach(ele => {  if (mp.has(ele) && mp.get(ele) === 1) {  mp.set(ele, 2);  }  });  // Mark all the elements which are common in first,  // second and third array with value = 3  arr3.forEach(ele => {  if (mp.has(ele) && mp.get(ele) === 2) {  mp.set(ele, 3);  }  });  let commonElements = [];  mp.forEach((value, key) => {  if (value === 3) {  commonElements.push(key);  }  });  return commonElements; } // Sample Input let arr1 = [ 1, 5, 10, 20, 30 ]; let arr2 = [ 5, 13, 15, 20 ]; let arr3 = [ 5, 20 ]; let common = commonElements(arr1, arr2, arr3); if (common.length == 0)  console.log(-1); console.log(common.join(" ")); 

5 20 

Time complexity: O((n1 + n2 + n3)*log n1), where inserting arr1[] takes O(n1 * log(n1)), and lookups for arr2[] and arr3[] take O(n2 * log(n1) + n3 * log(n1))
Auxiliary Space: O(n1)

[Expected Approach] Using three pointers - O(n1 + n2 + n3) Time and O(1) Space

We can efficiently find common elements in three sorted arrays using the three-pointer technique, eliminating the need for merging or intersecting the arrays.

Since the arrays are sorted in non-decreasing order, the smallest element among the three pointers at any moment will always be the smallest in the merged arrays. Leveraging this property, we can optimize our approach as follows:

• Initialize three pointers, one for each array.
• Compare the current elements at each pointer.
• If they are equal, it's a common element, store it and move all three pointers forward.
• Otherwise, move only the pointer pointing to the smallest element.
• Repeat the process until at least one array is fully traversed.

Working of Three pointers approach:

#include <bits/stdc++.h> using namespace std; vector<int> commonElements(vector<int> arr1, vector<int> arr2, vector<int> arr3) {  int i = 0, j = 0, k = 0;  int n1 = arr1.size(), n2 = arr2.size(), n3 = arr3.size();  vector<int> common;  while (i < n1 && j < n2 && k < n3)  {  if (arr1[i] == arr2[j] && arr2[j] == arr3[k])  {  common.push_back(arr1[i]);  i++;  j++;  k++;  while (i < n1 && arr1[i] == arr1[i - 1])  i++;  while (j < n2 && arr2[j] == arr2[j - 1])  j++;  while (k < n3 && arr3[k] == arr3[k - 1])  k++;  }  else if (arr1[i] < arr2[j])  i++;  else if (arr2[j] < arr3[k])  j++;  else  k++;  }  return common; } int main() {  vector<int> arr1 = {1, 5, 10, 20, 30};  vector<int> arr2 = {5, 13, 15, 20};  vector<int> arr3 = {5, 20};  vector<int> common = commonElements(arr1, arr2, arr3);  if (common.size() == 0)  cout << -1;  for (int ele : common)  {  cout << ele << " ";  }  return 0; } 

import java.util.ArrayList; import java.util.List; public class GfG {  static List<Integer>  commonElements(int[] arr1, int[] arr2, int[] arr3)  {  int i = 0, j = 0, k = 0;  List<Integer> common = new ArrayList<>();  while (i < arr1.length && j < arr2.length  && k < arr3.length) {  if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {  common.add(arr1[i]);  i++;  j++;  k++;  while (i < arr1.length  && arr1[i] == arr1[i - 1])  i++;  while (j < arr2.length  && arr2[j] == arr2[j - 1])  j++;  while (k < arr3.length  && arr3[k] == arr3[k - 1])  k++;  }  else if (arr1[i] < arr2[j])  i++;  else if (arr2[j] < arr3[k])  j++;  else  k++;  }  return common;  }  public static void main(String[] args)  {  int[] arr1 = { 1, 5, 10, 20, 30 };  int[] arr2 = { 5, 13, 15, 20 };  int[] arr3 = { 5, 20 };  List<Integer> common  = commonElements(arr1, arr2, arr3);  if (common.size() == 0)  System.out.print(-1);  for (int i = 0; i < common.size(); i++)  System.out.print(common.get(i) + " ");  } } 

# Function to find common elements in three arrays def commonElements(arr1, arr2, arr3): i, j, k = 0, 0, 0 common = [] while i < len(arr1) and j < len(arr2) and k < len(arr3): if arr1[i] == arr2[j] == arr3[k]: common.append(arr1[i]) i += 1 j += 1 k += 1 while i < len(arr1) and arr1[i] == arr1[i - 1]: i += 1 while j < len(arr2) and arr2[j] == arr2[j - 1]: j += 1 while k < len(arr3) and arr3[k] == arr3[k - 1]: k += 1 elif arr1[i] < arr2[j]: i += 1 elif arr2[j] < arr3[k]: j += 1 else: k += 1 return common # Sample Input arr1 = [1, 5, 10, 20, 30] arr2 = [5, 13, 15, 20] arr3 = [5, 20] common = commonElements(arr1, arr2, arr3) if len(common) == 0: print(-1) print(*common) 

using System; using System.Collections.Generic; class GfG {  static List<int> commonElements(int[] arr1, int[] arr2,  int[] arr3)  {  int i = 0, j = 0, k = 0;  List<int> common = new List<int>();  while (i < arr1.Length && j < arr2.Length  && k < arr3.Length) {  if (arr1[i] == arr2[j] && arr2[j] == arr3[k]) {  common.Add(arr1[i]);  i++;  j++;  k++;  while (i < arr1.Length  && arr1[i] == arr1[i - 1])  i++;  while (j < arr2.Length  && arr2[j] == arr2[j - 1])  j++;  while (k < arr3.Length  && arr3[k] == arr3[k - 1])  k++;  }  else if (arr1[i] < arr2[j])  i++;  else if (arr2[j] < arr3[k])  j++;  else  k++;  }  return common;  }  static void Main()  {  int[] arr1 = { 1, 5, 10, 20, 30 };  int[] arr2 = { 5, 13, 15, 20 };  int[] arr3 = { 5, 20 };  List<int> common = commonElements(arr1, arr2, arr3);  if (common.Count == 0)  Console.Write(-1);  Console.WriteLine(string.Join(" ", common));  } } 

// Function to find common elements in three arrays function commonElements(arr1, arr2, arr3) {  let i = 0, j = 0, k = 0;  let common = [];  while (i < arr1.length && j < arr2.length  && k < arr3.length) {  if (arr1[i] === arr2[j] && arr2[j] === arr3[k]) {  common.push(arr1[i]);  i++;  j++;  k++;  while (i < arr1.length  && arr1[i] === arr1[i - 1])  i++;  while (j < arr2.length  && arr2[j] === arr2[j - 1])  j++;  while (k < arr3.length  && arr3[k] === arr3[k - 1])  k++;  }  else if (arr1[i] < arr2[j])  i++;  else if (arr2[j] < arr3[k])  j++;  else  k++;  }  return common; } // Driver code function main() {  let arr1 = [ 1, 5, 10, 20, 30 ];  let arr2 = [ 5, 13, 15, 20 ];  let arr3 = [ 5, 20 ];  let common = commonElements(arr1, arr2, arr3);  if (common.length == 0)  console.log(-1);  console.log(common.join(" ")); } main(); 

5 20