6
\$\begingroup\$

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)\$?

\$\endgroup\$
10
\$\begingroup\$

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++;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Should it be else if(sorted1[index1] > sorted2[index2]) { index2++ }? \$\endgroup\$ – h.j.k. Jan 23 '15 at 16:44
  • \$\begingroup\$ @h.j.k. think you're right there. if the first array's value is greater, you have to increment index2 because there is no way for that second array's value to be in the first array \$\endgroup\$ – committedandroider Jan 23 '15 at 16:57
5
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

Are you allowed to use built-in functions? If that is the case you can use the retainAll() method.

Integer[] sorted1 = { 1, 2, 3, 5, 7 };
Integer[] sorted2 = { 2, 4, 5, 6 };

List<Integer> duplicates = new ArrayList<Integer>(Arrays.asList(sorted1));
duplicates.retainAll(Arrays.asList(sorted2));

System.out.println("Duplicates: " + duplicates);
//Output: Duplicates: [2, 5]
\$\endgroup\$
  • 2
    \$\begingroup\$ This is still O(n^2) because retainAll doesn't check whether the arrays are sorted so it needs to check all against all. \$\endgroup\$ – ratchet freak Jan 23 '15 at 9:47
  • \$\begingroup\$ I didn't know that as I am not that familiar with Java, thanks for the comment! ;) \$\endgroup\$ – Abbas Jan 23 '15 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.