Developing a Faster Intersection Algorithm Scenario We havealready seen an algorithm that produces an intersection between twoinput arrays in Snippet 1.6, shown below:

public List intersection(int[] a, int[] b) {

List result = new ArrayList<>(a.length);

for(int x : a) {

for(int y : b) {

if (x == y) result.add(x);

}

}

return result;

}

We have already shown how the runtime complexity of thisalgorithm is O(n2). Can we write an algorithm with a faster runtimecomplexity?

To find a solution for this problem, think about how you wouldyou go about finding the intersection by hand between two decks ofplaying cards. Imagine you take a subset from each shuffled deck;which technique would you use to find the common cards between thefirst and second deck?

Aim

Improve the performance of the array intersection algorithm andreduce its runtime complexity.

Prerequisites

You will find two methods for improving the intersection: Theslow intersection:

public List intersection(int[] a, int[] b)

The empty stub, returning null: public ListintersectionFast(int[] a, int[] b)

Use the second, empty stub method, to implement a fasteralternative for the intersection algorithm.

Assume that each array has no duplicate values.

Steps for Completion

Assume that we have a way to sort the inputs in O(n log n). Thisis provided in the following method:

public void mergeSort(int[] input) {

Arrays.sort(input);

}

We can use this method to sort one input array, or both, andmake the intersection easier.

To sort one input array, we can use a binary search on it. Theruntime complexity is O(n log n) for the merge sort plus O(n log n)for the binary search per item in the first list. This is nlog+nlog n which results in a final O(n log n).

Sort both arrays, and have two pointers, one for each array.

Go through the input arrays in a linear fashion. Advance apointer if the other pointer is pointing to a larger value.

If the values at both pointers are equal, both pointers areincremented. The runtime complexity for this algorithm is 2 (n logn) for the two merge sorts plus the n for the linear pass after thesorting. This results in 2 (n log n) + n with a final O(n logn).

CODE TO WORK WITH:

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class SimpleIntersection {

private BinarySearch search = new BinarySearch();

public List intersection(int[] a, int[] b){
List result = new LinkedList<>();
for (int x : a) {
for (int y : b) {
if (x == y) result.add(x);
}
}
return result;
}

public List intersectionFast(int[] a, int[] b){
// Write your code here
return null;
}

public void mergeSort(int[] input) {
Arrays.sort(input);
}

public static void main(String[] args) {
Intersection inter = new Intersection();
System.out.println(inter.intersection(new int[]{4, 7, 5, 2, 3}, newint[]{4, 2, 3, 9, 1}));
System.out.println(inter.intersection(new int[]{4, 6, 11, 2, 3},new int[]{5, 11, 3, 9, 1}));

// Write your code here

}
}