Find the maximum element which is common in two arrays?

Question

Given two arrays, how to find the maximum element which is common to both the arrays?

I was thinking of sorting both the arrays(n log n) and then perform the binary search of every element from one sorted array(starting from larger one) in another array until match is found.

eg:

a = [1,2,5,4,3]
b = [9,8,3]

Maximum common element in these array is 3

Can we do better than n log n?

Answer 1

With some extra space you could hash in 1 array, then do a contains on each element of the other array keeping track of the biggest value that returns true. Would be O(n).

Answer 2

You can but using O(N) space.
Just go through the first array and place all elements in a HashTable. This is O(N)
Then go through the second array keeping track of the current maximum and checking if the element is in the HashTable. This is also O(N) . So total runtime is O(N) and O(N) extra space for the HashTable

Example in Java:

public static int getMaxCommon(int[] a, int[] b){  
  Set<Integer> firstArray = new HashSet<Integer>(Arrays.asList(a));  
  int currentMax = Integer.MIN_VALUE;  
  for(Integer n:b){  
     if(firstArray.contains(n)){  
         if(currentMax < n){  
              currentMax = n  
         }
     }   
  }   
  return currentMax;  
}