Given two arrays A and Q, foreach element of of Q, find the element in A with smallest difference

Given 2 unsorted array A and Q of differing length. For each element in Q, find a element in A that has the smallest differences.

int[] findSmallestDifference(int A[], int Q[]){
   int []result = new int[Q.length];
   // insert code to find difference for each Q
   return result;
}

I encountered this problem during a interview, which I provided a couple of solution, but it was mentioned that it wasn't optimal yet.

Solutions I provided:

  1. Brute force: foreach A, foreach Q compute difference, O(A*Q)
  2. Sort Array A, foreach element of Q, perform binary search to find smallest difference, O(AlogA + QlogA)
  3. Sort both A and Q, then we have two pointer on each array to find difference, O(AlogA + QlogQ)

What is the optimal solution that I haven't thought of?

2 answers

  • answered 2018-07-18 09:40 Gijs Den Hollander

    The following method can be faster it depends on the data in the arrays. But lets say you have the following two arrays.

    A = {1,2,5,11,13} and Q = {3,5,12}

    Create two new arrays and fill the array so that the value in old array is the index is in the new array. So the size of the new array is largest number in the old array, repeating values are ignored. For example:

    an example how it should work (pseudo code):

    A'=null
    Q'=null
    
    A' and Q' have the size of the largest number in A or Q
    for i < length(A) i++ {
       A'[A[i]]=A[i]
       B'[B[i]]=B[i]
    } 
    
    A'= {1,2,null,null,5,null,....,null,11,null,13}
    Q'= {null,null,3,null,5,null,....,12,null}
    
    for i < length(A') i++ {
        if(A[i] == Q[i]){ 
           print(A[i])
        } else if (A[i] == null) {
           for(j=1 j < length(A') j++) {
              if(Q[i+j] != null || Q[i-j] != null){ //here you have to be carfull nto go to -negative indices
                  print[Q[i-j],Q[i+j],A[i]]
                  Break;
              }
           }
        }
    
    }
    

    And then compare the two array's to see if the index of the values are filled.If there not filled find the next index which is filled.

    This method speed depends on how sparse the numbers of two array's are distributed. If you have very huge numbers (and far apart) this is probably very sub optimal.

    The best case scenario of this algorithm is O(A+Q), the worst case scenario is O(infinite).

  • answered 2018-07-18 11:32 SaiBot

    I have sketch for an idea for the case where |Q| < |A| based on Quickselect. The idea would be to partially sort A while successively processing the elements in Q by searching for the element with the smallest difference in A.

    So for the first element in Q you perform a quickselect like search in order to find the element with the smallest difference. This search will cost O(A) but partially sort the elements in Q. The second element in Q will already profit from the first search and further sort A.

    I am currently not sure how to calculate the runtime complexity but it could be better than O(A log A) since A will not necessarily be sorted completely after processing all elements in Q. In the best case it could be O(Q log A).

    Not sure if it helps, but maybe someone can figure out the missing parts.