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.

Next Post Previous Post