Common Element in 3 sorted array

Given three arrays sorted in increasing order. Find the elements that are common in all three arrays.
Note: can you take care of the duplicates without using any additional Data Structure?

Example 1:
Input:
n1 = 6; A = {1, 5, 10, 20, 40, 80}
n2 = 5; B = {6, 7, 20, 80, 100}
n3 = 8; C = {3, 4, 15, 20, 30, 70, 80, 120}
Output: 20 80
_Explanation: 20 and 80 are the only
common elements in A, B and C.
_
Example 2:
Input:
_n1=3; A={3, 3, 3}
n2=3; B={3, 3, 3}
n3=3; C={3, 3, 3}
_Output: 3

This question was asked in companies like MAQ Software, Microsoft ,VMWare

To solve this question click here:(https://practice.geeksforgeeks.org/problems/common-elements1132/1#)

Approach 1:
Time Complexity: O(n1+n2+n3)
Space Complexity: O(1)
In this we have used three pointer i, j, k to iterate through the 3 sorted array.

import java.util.*;

public class commonEle_in_3sorted {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter n1: ");
        int n1 = sc.nextInt();
        System.out.print("Enter n2: ");
        int n2 = sc.nextInt();
        System.out.print("Enter n3: ");
        int n3 = sc.nextInt();
        int[] A = new int[n1];
        int[] B = new int[n2];
        int[] C = new int[n3];
        System.out.println("Enter the elements of the array A: ");
        for (int i = 0; i < n1; i++) {
            A[i] = sc.nextInt();
        }
        System.out.println("Enter the elements of the array B: ");
        for (int i = 0; i < n2; i++) {
            B[i] = sc.nextInt();
        }
        System.out.println("Enter the elements of the array C: ");
        for (int i = 0; i < n3; i++) {
            C[i] = sc.nextInt();
        }
        M1commonElement(A, B, C, n1, n2, n3);
    }

    public static void M1commonElement(int A[], int B[], int C[], int n1, int n2, int n3) {
        int i = 0, j = 0, k = 0;
        ArrayList<Integer> al = new ArrayList<>();
        while (i < n1 && j < n2 && k < n3) {
            if (A[i] == B[j] && A[i] == C[k]) {
                al.add(A[i]);// common element
                int ele = A[i];
                // to remove duplicacy
                while (i<n1 && A[i]==ele)
                    i++;
                while (j<n2 && B[j] == ele)
                    j++;
                while (k<n3 && C[k] == ele)
                    k++;
            } 
            else if (A[i] < B[j])
                i++;
            else if (B[j] < C[k])
                j++;
            else
                k++;

        }
        for (int ele : al) {
            System.out.println(ele);
        }
    }

Approach 2:
Time Complexity: O(n1+n2+n3)
Space Complexity: O(n1+n2+n3)
In this we have use HashMap to store the three sorted array. And then we have again iterated through the loop and checked if that element is present in the HashMap (hm1,hm2,hm3) or not.

 public static void M2commonElement(int A[], int B[], int C[], int n1, int n2, int n3) {
        HashMap<Integer, Integer> hm1 = new HashMap<>();
        HashMap<Integer, Integer> hm2 = new HashMap<>();
        HashMap<Integer, Integer> hm3 = new HashMap<>();
        for (int i = 0; i < n1; i++)
            hm1.put(A[i], i);
        for (int i = 0; i < n2; i++)
            hm2.put(B[i], i);
        for (int i = 0; i < n3; i++)
            hm3.put(C[i], i);

        ArrayList<Integer> arr = new ArrayList<>();
        for (int i = 0; i < n1; i++) {
            if (hm1.containsKey(A[i]) && hm2.containsKey(A[i]) && hm3.containsKey(A[i])) {
                arr.add(A[i]);
                hm1.remove(A[i]);
            }
        }
        for (int ele : arr)
            System.out.print(arr);
    }

Comments

[Alex Lohr]

Simple JS variant for an arbitrary number of arrays:

const commonItems = (start, ...others) =>
  start.filter(item => others.every(
    array => array.includes(item)
  ))

Optimized version:

const commonItems = (start, ...others) => {
  const maps = others.map(array =>
    new Map(array.map(item => [item, true]))
  )
  return start.filter(item => maps.every(
    array => array.has(item)
  ))
}

[peerreynders]

Just for fun:

const list = [
  [1, 5, 10, 20, 40, 80],
  [6, 7, 20, 80, 100],
  [3, 4, 15, 20, 30, 70, 80, 120],
];
console.log(intersectList(list)); // [20, 80]

function intersect(last, values) {
  const collectCommon = (common, value) =>
    last.has(value) ? common.add(value) : common;
  return values.reduce(collectCommon, new Set());
}

function intersectList(list) {
  const [head, ...tail] = list;
  if (tail.length === 0) return typeof head === 'undefined' ? [] : head;

  return [...tail.reduce(intersect, new Set(head))];
}

For the more imperatively minded:

function intersectList(list) {
  const [head, ...tail] = list;
  if (tail.length === 0) return typeof head === 'undefined' ? [] : head;

  let last = new Set(head);
  for (const xs of tail) {
    const common = new Set();
    for (const x of xs) if (last.has(x)) common.add(x);
    last = common;
  }
  return [...last];
}