Question

Developing a Faster Intersection Algorithm Scenario We have already seen an algorithm that produces an intersection between two input 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 this algorithm is O(n2). 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

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

Prerequisites

You will find two methods for improving the intersection: The slow intersection:

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

The empty stub, returning null: public List 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.

Steps for Completion

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.

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).

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

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

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).

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<Integer> intersection(int[] a, int[] b) {
List<Integer> result = new LinkedList<>();
for (int x : a) {
for (int y : b) {
if (x == y) result.add(x);
}
}
return result;
}

public List<Integer> 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}, new int[]{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

}
}

Answer 1

Points to consider:

1. We need to sort the array
2. Then we need to traverse both the arrays together.
3. appending the common ones to the list.

Code

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

public class SimpleIntersection {

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

public List<Integer> intersectionFast(int[] a, int[] b) {
// Write your code here
   mergeSort(a);
   mergeSort(b);
   List<Integer> list = new ArrayList<Integer>();
   int i =0, j = 0;
   while(i<a.length && j<b.length)
   {
       if(a[i]<b[j]) {
           i++;
       }
       else if(a[i] > b[j]) {
           j++;
       }
       else {
           list.add(a[i]);
           i++;j++;
       }
   }
   return list;
}

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

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

// Write your code here

}
}

Sample output:

Friend, That was a nice question to answer
If you have any doubts in understanding do let me know in the comment section. I will be happy to help you further.
Please like it if you think effort deserves like.
Thanks