#### Common elements of multiple arrays 2

Given two arrays A and B, find common elements of these 2 arrays. Size of array `A` and `B` is M and N respectively. In general given multiple arrays, find common elements of all of them.

Example:

``````A = {2, 3, 1, 7}
B = {5, 2, 1, 7, 8, 9}
Result = {2, 1, 7}``````

Approach 1:

Lets assume array `A` is smaller array and `B` is larger array.

1. Sort the smaller array `A`.
2. Traverse each element of larger array `B`. Find element in the sort array `A`. If found take this element.

Complexity: O(M lg M) + O(N lg M)

Code:

``````import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class IntersectionArray {

static int nA, nB;
static int[] A, B;

static int binarySearch(int[] arr, int x) {
int low = 0, high = arr.length-1;
while (low <= high) {
int mid = (low + high) / 2;
if (x < arr[mid]) high = mid-1;
else if (x > arr[mid]) low = mid + 1;
else return mid;
}
return -1;
}

static List<Integer> intersectArrays(int[] A, int[] B) {
Arrays.sort(A);
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < B.length; i++) {
if (binarySearch(A, B[i]) != -1) list.add(B[i]);
}
return list;
}

public static void main(String[] args) {
Scanner scanner = inputFromFile();
nA = scanner.nextInt();
nB = scanner.nextInt();

A = new int[nA];
B = new int[nB];

for (int i = 0; i < nA; i++) A[i] = scanner.nextInt();
for (int i = 0; i < nB; i++) B[i] = scanner.nextInt();

List<Integer> list = intersectArrays(A, B);

for (int i = 0; i < list.size(); i++) System.out.print(list.get(i) + " ");
}

static Scanner inputFromFile() {
try { return new Scanner(new FileInputStream("input.txt")); }
catch (FileNotFoundException e) { e.printStackTrace(); }
return null;
}

static Scanner inputFromSystem() {
return new Scanner(System.in);
}
}``````

Approach 2:

Using `HashSet` will reduce time complexity.

1. Add all elements of array `A` into set `S`.
2. Traverse all elements of array `B`. If element found in `A` take this element.

Complexity: O(M + N)

Code:

``````static List<Integer> intersect(int[] arr1, int[] arr2) {
HashSet<Integer> set = new HashSet<>();

for (int i = 0; i < arr1.length; i++) set.add(arr1[i]);

List<Integer> ret = new ArrayList<>();
for (int i = 0; i < arr2.length; i++) {
if (set.contains(arr2[i])) ret.add(arr2[i]);
}

return ret;
}``````

For multiple arrays we can use same HashSet technique:

Code:

``````static List<Integer> intersectArrays(int[][] arrays) {
int arrayCount = arrays.length;
Set<Integer> set = new HashSet<>();

for (int i = 0; i < arrays[0].length; i++) set.add(arrays[0][i]);

for (int i = 1; i < arrays.length; i++) {
HashSet<Integer> tmpSet = new HashSet<>();
for (int j = 0; j < arrays[i].length; j++) {
if (set.contains(arrays[i][j])) tmpSet.add(arrays[i][j]);
}
set = tmpSet;
}

return set.stream().collect(Collectors.toList());
}``````
Blog Comments powered by Disqus.