21
$\begingroup$

Title states the question.

We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal.

Key points:

  1. Comparison is not transitive (think rock paper scissors): this can be true: A > B, B > C, C > A (note this is not a valid input since there is no valid answer here, I'm only describing what "non-transitive comparison" means)
  2. Each input array will is guaranteed to have an answer
  3. greatest means the element must be greater than every other element
  4. Converse property holds i.e. A > B implies that B < A

Example:

Input: [A,B,C,D]
A > B, B > C, C > A
D > A, D > B, D > C
Output: D

I cannot figure out a way to do this in O(n) time, my best solution is O(n^2).

I get stuck on every approach because of the fact that to be certain of an answer, the element needs to be explicitly compared to every other element, to prove it is indeed the answer (because comparison is not transitive).

This rules out the use of a heap, sorting, etc.

$\endgroup$
  • 8
    $\begingroup$ It is unclear how "the greatest element" would be defined? For example, which element is the greatest if $A > B, B > C, C > A$? Do you have any other rules of comparison? $\endgroup$ – fade2black Nov 20 '17 at 17:51
  • 6
    $\begingroup$ I can't imagine how we would select the greatest element in a set which is not at least partially ordered. Please see the definition of the greatest and least element. Lack of transitivity rules out partial order. $\endgroup$ – fade2black Nov 20 '17 at 17:59
  • 3
    $\begingroup$ @fade2black Why are you linking me to another definition of "greatest". I'm explicitly stating the definition of greatest for the context of this question. Greatest means, the element is greater than every other element. No element is equal. That is all there is to it. Is this not clear? $\endgroup$ – James Wierzba Nov 20 '17 at 18:00
  • 2
    $\begingroup$ Your last example with A,B,C,D would be helpful to understand you question if you included it in your OP. $\endgroup$ – fade2black Nov 20 '17 at 19:30
  • 3
    $\begingroup$ A member of the C# compiler team used to ask this as an interview question; it is relevant because in C#, the overload resolution algorithm must pick the unique best member of a set given a "betterness" relation that is usually, but not necessarily transitive. (Or give a suitable response if there is no such unique best member; ties are possible.) Though I managed to answer it correctly, I never thought it was a particularly good interview question since it relies upon an "aha" insight to get the linear algorithm. $\endgroup$ – Eric Lippert Nov 21 '17 at 17:32
38
$\begingroup$

The standard algorithm for finding a maximum still works. Start with $a_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every element you skipped is smaller than at least one element, and can thus not be the maximum.

To be clear, by the "standard algorithm" I mean the following:

max <- a_1
for i=2 to n
   if a_i > max
      max <- a_i
output max

For completeness, I will discuss here the issues raised in the comments. The setting in the above discussion is finding a maximum relative to an anti symmetric relation $<$, where $a_i$ is a maximum if for all $j\neq i$ we have $a_i>a_j$. The above algorithm works under the assumption that a maximum exists, however if this is not known, one can use it to verify the existence of a maximum (check whether the returned element is indeed greater than all other elements, this is mentioned in Chi's comment and in Ilmari Karonen answer).

If $<$ is not necessarily anti symmetric, then the above algorithm fails (as Emil mentioned in the comments). If $<$ is an arbitrary relation (i.e. we are relaxing both transitivity and anti symmetry), then it is not hard to show that finding a maximum in linear time is not possible. Denote by $\#a_i$ the number of times $a_i$ participated in a query, we define an adversarial relation in a way that the maximum cannot be revealed without enough queries. Given the query $a_i >?a_j $, answer $a_i>a_j$ if $\# a_i < n-1$ and $a_i<a_j$ otherwise. If the number of queries is $o(n^2)$, then a maximum was not yet seen, and it can be set to be either of the elements in the set.

$\endgroup$
  • 1
    $\begingroup$ @JamesWierzba (I think) he just means a "skipped" element is one that's not greater than your current max. Consider the standard algorithm: you check each value in your list against the current maximum. You've said there's a greatest element in each list. At some point, you'll compare that against your current maximum, and since it's larger, that value becomes your new maximum. Because this value is greater than everything else in the list, you'll never find an element which is greater, and your greatest value won't be replaced. After your n comparisons, your current max has to be the answer $\endgroup$ – Lord Farquaad Nov 20 '17 at 21:54
  • 1
    $\begingroup$ Edited for clarity, this algorithm does not assume transitivity. If you find that hard to believe, follow the details of the correctness proof (assume for the purpose of contradiction that the returned value is not the maximum, and use the idea from the first paragraph). $\endgroup$ – Ariel Nov 20 '17 at 23:59
  • 7
    $\begingroup$ This relies on assumption 2 in the question: there is always a maximum in the array. If this were not the case, max could only be the maximum of a subarray. Still, even without assumption 2, one can find a tentative maximum, and then verify it on the whole array using a second scan, within the O(n) bound. $\endgroup$ – chi Nov 21 '17 at 8:39
  • 7
    $\begingroup$ This answer assumes that $A>B$ and $B>A$ cannot hold at the same time. As far as I can see, this is not ruled out in the question. $\endgroup$ – Emil Jeřábek Nov 21 '17 at 17:46
  • 4
    $\begingroup$ @oconnor0 That does not follow. For a concrete example, assume A > B, A > C, B > A, and C > B. Then A is greater than any other element in the set (and is the only element with this property), but if the elements are encountered in the order A, B, C, the algorithm will output C. $\endgroup$ – Emil Jeřábek Nov 21 '17 at 22:36
24
$\begingroup$

As Ariel notes, the standard maximum-finding algorithm given below:

def find_maximum(a):
    m = a[0]
    for x in a:
        if x > m: m = x
    return m

will in fact work without modification as long as:

  • any pair of elements can be compared, and
  • the input is guaranteed to contain a maximal element, i.e. an element that is pairwise greater than any other element in the input.

(The first assumption above can actually be relaxed, even without having to modify the algorithm, as long as we assume that the maximal element is comparable with every other element and that x > y is always false if the elements x and y are incomparable.)

In particular, your claim that:

[…] to be certain of an answer, the element needs to be explicitly compared to every other element (because comparison is not transitive).

is not true under the assumptions given above. In fact, to prove that the algorithm above will always find the maximal element, it's sufficient to observe that:

  1. since the loop iterates over all the input elements, at some iteration x will be the maximal element;
  2. since the maximal element is pairwise greater than every other element, it follows that, at the end of that iteration, m will be the maximal element; and
  3. since no other element can be pairwise greater than the maximal element, it follows that m will not change on any of the subsequent iterations.

Therefore, at the end of the loop, m will always be the maximal element, if the input contains one.


Ps. If the input does not necessarily always contain a maximal element, then verifying that fact will indeed require testing the candidate answer against every other element to verify that it is really maximal. However, we can still do that in O(n) time after running the maximum-finding algorithm above:

def find_maximum_if_any(a):
    # step 1: find the maximum, if one exists
    m = a[0]
    for x in a:
        if x > m: m = x

    # step 2: verify that the element we found is indeed maximal
    for x in a:
        if x > m: return None  # the input contains no maximal element
    return m  # yes, m is a maximal element

(I'm assuming here that the relation > is irreflexive, i.e. no element can be greater than itself. If that's not necessarily the case, the comparison x > m in step 2 should be replaced with x ≠ m and x > m, where denotes identity comparison. Or we could just apply the optimization noted below.)

To prove the correctness of this variation of the algorithm, consider the two possible cases:

  • If the input contains a maximal element, then step 1 will find it (as shown above) and step 2 will confirm it.
  • If the input does not contain a maximal element, then step 1 will end up picking some arbitrary element as m. It doesn't matter which element it is, since it will in any case be non-maximal, and therefore step 2 will detect that and return None.

If we stored the index of m in the input array a, we could actually optimize step 2 to only check those elements that come before m in a, since any later elements have already been compared with m in step 1. But this optimization does not change the asymptotic time complexity of the algorithm, which is still O(n).

$\endgroup$
  • 3
    $\begingroup$ In fact the OP skips many details. For example, nothing is said about reflexivity of the relation, and so if it is not reflexive then if x > m: is undefined. $\endgroup$ – fade2black Nov 20 '17 at 22:26
4
$\begingroup$

"greatest means the element must be greater than every other element" is a huge hint on how to do this in $O(n)$.

If you go through your list comparing elements, any element that "loses" a comparison can be immediately discarded as, in order to be the greatest, it must be greater than ALL other elements so the single loss disqualifies it.

Once you think of it in that manner, then it's pretty obvious that you actually can make $n-1$ comparisons and end up with the greatest element as the result of your last comparison, by discarding a loser each and every time.

This solution is enabled by a subtlety: "No element can be equal" combined with the fact that there will always be a greatest element. If we map wins relationships as a directed graph, it is clear that we can reach the greatest element simply by following the wins.

$\endgroup$
  • 1
    $\begingroup$ "Acyclic directed graph" is the wrong model: it should instead be "tournament". Cycles are permitted, and it's crucial that every edge exists in exactly one direction. $\endgroup$ – Peter Taylor Nov 22 '17 at 11:05
  • $\begingroup$ @PeterTaylor you're absolutely right, I was only thinking about the wins that lead towards the 'greatest' element, the other wins are less relevant but may be traversed on the path to discovering the greatest so you're right that they can't be discounted $\endgroup$ – Danikov Nov 22 '17 at 13:03
3
$\begingroup$

I assume that the relation antisymmetric for at least a single element (which guarantees the existence of the greatest element), otherwise the task is impossible. If all elements in the finite set are comparable then usual finding-maximum procedure works.

If some elements are not comparable then the following procedure will work

max = nil
For i=1 to n
   if max is nil then
      max = a[i]
   if max and a[i] are not comparable then
      max = nil
   else if max < a[i] then
      max = a[i]
End

This is how the algorithm will work on input $A,B,C,D$ with $$A > B, B > C, C > A $$ $$D > A, D > B, D > C$$ as in your post.

Initially. max = nil
$i=1:$ $\max = A$
$i=2:$ $\max = A$ (since $A > B$)
$i=3:$ $\max = C$ (since $A < C$)
$i=4:$ $\max = D$ (since $D > C$)

This algorithm works since if $m>a$ (or $a < m$) for all $a$ then $m$ is the greatest. If $m<a$ for some element $a$ then $m$ cannot be the greatest. Similarly, if $a$ and $m$ are not comparable then they both cannot be the greatest. This procedure would work even if all elements are comparable.

$\endgroup$
  • $\begingroup$ I don't think the first else if is needed. It cannit be triggered if max is the maximum, and if the maximum has not yet been encountered it doesn't matter what the value of max is. $\endgroup$ – rici Nov 20 '17 at 20:06
  • $\begingroup$ Yes, that is the first one. The other one is the second one :) $\endgroup$ – rici Nov 20 '17 at 20:09
  • $\begingroup$ You mean leave ifs without elses? It is just a habit: with elses we do not even compare. :) $\endgroup$ – fade2black Nov 20 '17 at 20:11
  • 1
    $\begingroup$ Wouldn't it be simpler to just initialize max to any element of the list and, inside the loop, do if max and a[i] are comparable and max < a[i] then max = a[i] (where the first part of the condition could be omitted if we assume that trying to compare two incomparable elements always yields false)? $\endgroup$ – Ilmari Karonen Nov 20 '17 at 22:12
  • 1
    $\begingroup$ @badallen the OP assumes that there is always the greatest element. In your example there is no greatest element. $\endgroup$ – fade2black Nov 21 '17 at 19:27
2
$\begingroup$

As an addition to Ariel's answer about the concerns raised by Emil Jeřábek: If we allow $A<B$ and $B<A$ then there is no O(n) algorithm:

Assume you have elements $A_1 ... A_n$. Your algorithm will in each step query $A_i<A_j$ for some pair i and j. No matter in which order you query them, there is always a relation where you have to query all relations before finding the maximum. The reason for this is best described by assuming you have an adversary who can change the problem while your algorithm is running.

(Note that the argument is independent of what the algorithm actually does with the information he gets about the elements, since it explains that he cannot know that an element is maximal before making $n^2$ queries.)

For most of the algorithm the adversary will make sure to always return true for $A_i<A_j$ until your last query for a given $j$. Note that you cannot know that one given element is maximal until you compared it to all other elements. Only for the last element for which you finish all relations the adversary will return true for the last element as well.

The resulting relation will always be such that there is some $j_0$ for which $A_i < A_{j_0}\forall i$ and for all other $j$ there will be some $i_j$ such that $A_i<A_j \forall i\neq i_j$ and we will not have $A_{i_j} < A_j$. The adversary chooses $j_0$ and the $i_j$s depending on your algorithm.

I hope this is somewhat understandable. Feel free to ask in comments or edit.

The basic idea is that you cannot gather any information about the remaining elements from the ones you already know if you allow a completely arbitrary relation.

The argument still works if we disallow $A<A$. We will only save $n$ queries that way and still need $n^2-n$.

$\endgroup$
1
$\begingroup$

I'm going to cheat and call the number of A > B entries $n$ and you need to look at every entry at least once.

That way you can loop over just the entries and remove the element that is less than the other from the set of possible solutions. With a hashset or similar this is possible in $O(n)$

$\endgroup$

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.