Intersection And Union Of Arrays

INPUT : Two Arrays "A" and "B" consisting of "n" and "m" elements respectively.

OUTPUT :
The union "U" of the two arrays and the intersection "I" of the arrays.
Example : if A = {1, 2, 4, 8}, B = {2, 6, 8, 10} then,
                U = {1, 2, 4, 6, 8, 10}, I = {2, 8}
Note : Since arrays are fundamentally different from Sets in the sense that every element is unique, we neglect the repeating elements in the union and the intersection as well i.e. if A = {1, 1, 1} and B = {1, 1} then, U = {1, 1, 1, 1, 1} and I = {1, 1}. This is because each element in an array is fundamentally unique.

OUR APPROACH :
 The first step is to sort each array in the same order (we used quick-sort to sort the array in ascending order). For each of the 2 functions (union and intersection), we maintain 2 pointers, one for each array. Now, we compare the elements at the ith position of A and jth position of B. Since the arrays are in increasing order, we know that if A[ i ] < B[ j ], the value equal to B[j] will be found only on the right side of i and vice versa. Thus, we traverse the 2 arrays and store the required elements.

The Java code for the said functions is as follows:
The Java implementation of QuickSort can be found here .

	import java.util.Scanner;
	public class IntersectionAndUnionOfArray {
	public static void main(String[] args){
	Scanner in = new Scanner(System.in);
	System.out.println("Enter the length of the first array");
	int n = in.nextInt();
	System.out.println("Enter the first array");
	int[] a = new int[n];
	for (int i = 0; i < n; i++) {
	a[i] = in.nextInt();
	}
	System.out.println("Enter the length of the second array");
	n = in.nextInt();
	int[] b = new int[n];
	for (int i = 0; i < n; i++) {
	b[i] = in.nextInt();
	}
	QuickSort.quickSort(a, 0, a.length-1);
	QuickSort.quickSort(b, 0, n-1);
	int[] u = union(a, b);
	System.out.println("The union of the 2 arrays is:");
	for (int i = 0; i < u.length; i++) {
	System.out.print(u[i] + "\t");
	}
	int[] x = intersection(a, b);
	System.out.println("\nThe intersection of the 2 arrays is:");
	for (int i = 0; i < x.length; i++) {
	System.out.print(x[i] + "\t");
	}
	}
	public static int[] union(int[] a,int[] b){
	int [] u = new int[a.length+b.length];
	int i = 0, j = 0; //i will traverse a and j will traverse b
	int index = 0; //current index in u
	while((i < a.length) || (j < b.length)){
	if(j >= b.length){
	u[index++] = a[i++];
	}
	else if(i >= a.length){
	u[index++] = b[j++];
	}
	else if(a[i] < b[j]){
	u[index++] = a[i++];
	}
	else if(b[j] < a[i]){
	u[index++] = b[j++];
	}
	else{
	u[index++] = a[i++];
	j++;
	}
	}
	if(index < u.length){
	int[] u1 = new int[index];
	for (int k = 0; k < u1.length; k++) {
	u1[k] = u[k];
	}
	return u1;
	}
	else{
	return u;
	}
	}
	public static int[] intersection(int[] a, int[] b){
	int[] u = new int[Math.min(a.length, b.length)];
	int i = 0, j = 0;
	int index = 0;
	while((i < a.length) && (j < b.length)){
	if(a[i] < b[j]){
	i++;
	}
	else if(b[j] < a[i]){
	j++;
	}
	else{
	u[index++] = a[i++];
	j++;
	}
	}
	if(index < u.length){
	int[] u1 = new int[index];
	for (int k = 0; k < u1.length; k++) {
	u1[k] = u[k];
	}
	return u1;
	}
	else{
	return u;
	}
	}
	}

view raw Union And Intersection Of Arrays hosted with ❤ by GitHub

Note that, if we ignore the running time of QuickSort, the running time of each of the two functions is O(n+m).