CODEWITHSUNDEEP
algorithm
sushil
sushil

Reputation: 2671

Find the maximum element which is common in n different arrays?

Earlier today I asked similar problem to find the maximum element which is common in two arrays. I got a couple of good solutions here ( Find the maximum element which is common in two arrays?).

Now it occurred to me, what if instead of two arrays we have to find the maximum element which is common in n different arrays?

Example:

 array1 = [1,5,2,4,6,88,34]
 array2 = [1,5,6,2,34]
 array3 = [1,34]
 array4 = [7,99,34]

Here the maximum element which is common in all the arrays is 34.

Is it a good idea to create a hashmap of the array1, array2 ..... array(N-1) separately and then check every element of arrayN in each of these hashmaps keeping track of maximum element (when present in all the hashmaps)?

Can we have better solutions than this?

Upvotes: 0

Views: 187

Answers (2)

Running Wild
Running Wild

Reputation: 3011

For each array A_n:
  Add all elements in A_n to a hashset, H_n

Create a hashmap, M, which maps values to counts.
For each hashset H_n:
  For each value, v, in H_n:
    M[v]++

Go through M for the highest value with count == N

This will run in O(n) time and space, where n is the total number of elements in all arrays. It also properly deals with elements being duplicated in a single array, which you didn't mention but which might cause problems for some algorithms. If you know that you won't have duplicate elements in a single array you can skip the first step and add values to M directly from the arrays.

Upvotes: 1

DarthVader
DarthVader

Reputation: 55132

hashmap is not good to keep track of max elements. what you want is a max heap or hashset.

you create n max heap and you traverse n of them. you take the common max element. this might be hard to implement.

another approach would be to find the intersection of all the sets and take the max from the intersection. in this case, you can use hashset.

Upvotes: 0

Related Questions