DEV Community

Cover image for Common Element in 3 sorted array
Tisha Agarwal
Tisha Agarwal

Posted on

Common Element in 3 sorted array

#java #array #programming #beginners

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);
        }
    }
Enter fullscreen mode Exit fullscreen mode

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);
    }
Enter fullscreen mode Exit fullscreen mode

Top comments (2)

Collapse
 
lexlohr profile image
Alex Lohr •

Simple JS variant for an arbitrary number of arrays:

const commonItems = (start, ...others) =>
  start.filter(item => others.every(
    array => array.includes(item)
  ))
Enter fullscreen mode Exit fullscreen mode

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)
  ))
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
peerreynders profile image
peerreynders • • Edited

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))];
}
Enter fullscreen mode Exit fullscreen mode

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];
}
Enter fullscreen mode Exit fullscreen mode

Read next

ianbrumby profile image

Finally got some time to play with the new JSONata and Variables support for Step Functions, and I have to say, it is massive improvement. Check out my latest blog post, where I walk through a simple example of how easy it is to handle pagination now

Ian -

thisismemukul profile image

Getting Started with Golang: A Beginner’s Guide

Mukul Saini -

garciadiazjaime profile image

React 19: New hook useActionState

Jaime -

nodefiend profile image

Self Writing Lang Graph State

chowderhead -