Find the 'Best' element from the given list

Question

I was recently asked this question in one of my telephonic interview.

"There is a list of elements. And you have to find the "best" element from the list. The elements are comparable to each other, but the comparison is not transitive. E.g. if A > B and B > C, then A need NOT be greater than C.

You have to return the best element as answer, which is better than every other element in the list. It is possible, that there is no such element. In that case, return null."

My solution:

Attempt 1:

A simple O(n^2) solution. Comparison of each element with each other element.

The interviewer was not satisfied.

Attempt 2:

Start comparing first element with 2nd element and onward. For whichever element 'E', if A > E, mark E (may be by using another array/list/etc.) and do not consider E for any further comparison. This is because there is at least 1 element which is better than E, so E is definitely not the answer.

Complexity is still O(n^2) with some improvement as compared to previous attempt.

He was still not satisfied. Can anyone come up with any better solution?

Answer 1

Sure. You have N elements. Compare the first two. One of these is 'worse' than the other. Discard it. Compare the 'better' of the two with the next element. Continue this first pass across the list until only one element remains. This step is O(N).

The one element that survived the first pass now needs to be compared with every element from the original list except those that it was already compared with. If it 'loses' even once, you return that there is no 'best' element. If it 'wins' every comparison in this step you return this element. This step is also O(N).

This algorithm is O(N+N) = O(N) in the worst case and O(N+0) == O(N) in the best case. We can further prove that this is the best possible complexity because checking a solution is also O(N), and it cannot be less complex to get a solution than it is to check it.