Scenario

We have already seen an algorithm that produces an intersection between two input arrays in Snippet 1.6.

We have already shown how the runtime complexity of this algorithm is O(n²). Can we write an algorithm with a faster runtime complexity?

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

Aim

To improve the performance of the array intersection algorithm and reduce its runtime complexity.

Prerequisites

• Ensure that you have a class available at: 
  https://github.com/TrainingByPackt/Data-Structures-and-Algorithms-in-Java/blob/master/src/main/java/com/packt/datastructuresandalg/lesson1/activity/improveintersection/Intersection.java
• You will find two methods for improving the intersection:
  • The slow intersection:

public List<Integer> intersection(int[] a, int[] b)  

• • The empty stub, returning null:

public List<Integer> intersectionFast(int[] a, int[] b)  

• Use the second, empty stub method, to implement a faster alternative for the intersection algorithm.
• Assume that each array has no duplicate values. If you have your project set up, you can run the unit test for this activity by running the following command:

gradlew test --tests com.packt.datastructuresandalg.lesson1.activity.improveintersection*  

Steps for Completion

1. Assume that we have a way to sort the inputs in O(n log n). This is 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, and make the intersection easier.

2. To sort one input array, we can use a binary search on it. The runtime 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).
3. Sort both arrays, and have two pointers, one for each array.
4. Go through the input arrays in a linear fashion.
5. Advance a pointer if the other pointer is pointing to a larger value.
6. If the values at both pointers are equal, both pointers are incremented. The runtime complexity for this algorithm is 2 * (n log n) for the two merge sorts plus the n for the linear pass after the sorting. This results in 2 * (n log n) + n with a final O(n log n).