Finding duplicates in two sorted arrays

Question

This is an interview question from here. Specifically, the second asked for a function that took in two sorted arrays of integers with no duplicate values within a single array and which returned an array of the duplicates between the two arrays.

Here is my solution (with tests):

public class ArrayDuplicates {
     public static void main(String[] args) {
          int[] sorted1 = {1, 2, 3, 5, 7};
          int[] sorted2 = {2, 4, 5, 6};
          Integer[] duplicates = duplicates(sorted1, sorted2);
          for(Integer d: duplicates) {
            System.out.println(d.intValue());
           }
      }
     public static Integer[] duplicates(int[] sorted1, int[] sorted2) {
            List<Integer> duplicates = new ArrayList<Integer>();
            for(int count = 0; count < sorted1.length; count ++) {
                  for(int counter = 0; counter < sorted2.length; counter ++) {
                       if(sorted1[count] == sorted2[counter]) {
                            duplicates.add(sorted1[count]);
                       } else if(sorted1[count] < sorted2[counter]) {
                          break;
                       }
                   }    
             }
    return duplicates.toArray(new Integer[duplicates.size()]);
    }
}

The code runs fine but I am trying to make it more efficient. I did a runtime analysis of the duplicates method and found the runtime to be in \$O(N^2)\$ (general nested for loop, etc). To me, there always seems to be some optimization to get the algorithm to \$O(n)\$. For this problem, the only optimization, I found was to break out of the while loop if the value in the second array is greater than the first (because you know it's sorted, so there's no way that value is present in the second array).

Is there another optimization that could get this code down to \$O(n)\$?

Answer 1

You are looking for values in a sorted array, first thing that comes to mind is binary search (improves to \$O(n \log n)\$).

However because the values you look for are also sorted then you know that the next value will be after the value you found in the last iteration. Keep the index where you broke out of the inner loop and start there during the next iteration.

int innerIndex = 0;
for(int count = 0; count < sorted1.length; count ++) {
      for(; innerIndex < sorted2.length; innerIndex++) {
           if(sorted1[count] == sorted2[innerIndex]) {
                duplicates.add(sorted1[count]);
           } else if(sorted1[count] < sorted2[innerIndex]) {
              break;
           }
       }    
 }

Otherwise you can pretend to merge the arrays. It's essentially the same algorithm but makes it clearer what is happening:

int index1 = 0, index2
while(index1 < sorted1.length && index2 < sorted2.length){
    if(sorted1[index1] < sorted2[index2]){
        index1++;
    }else if(sorted1[index1] > sorted2[index2]){
        index2++;
    }else{
        duplicates.add(sorted1[index1]);
        index1++;
        index2++;
    }
}

Answer 2

To make this \$O(n)\$, the basic algorithm is to walk both arrays in one loop in parallel, in a merge-like manner.

That is, you start with index i=0 in the first array and j=0 in the second array, and you stop when one of your indexes moved past the end of its array. At each step in the single loop, you compare a[i] with b[j]. If a[i] is greater than b[j], you bump j by 1. If it is smaller, you bump i by 1. If a[i] is equal to b[j], you bump both i and j and record a[i] as a duplicate.

That's all. As each step results in at least one array element that will never be looked at again, this is \$O(n)\$.