patternMajor
in O(n) time: Find greatest element in set where comparison is not transitive
Viewed 0 times
greatestwheretransitivetimecomparisonelementfindnotset
Problem
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:
Example:
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.
We have as inputs a list of elements, that we can compare (determine which is greatest). No element can be equal.
Key points:
- 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)
- Each input array will is guaranteed to have an answer
- greatest means the element must be greater than every other element
- Converse property holds i.e. A > B implies that B
Example:
Input: [A,B,C,D]
A > B, B > C, C > A
D > A, D > B, D > C
Output: DI 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.
Solution
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:
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 $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 $?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.
To be clear, by the "standard algorithm" I mean the following:
max max
max <- a_i
output maxFor 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 $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 $?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.
Code Snippets
max <- a_1
for i=2 to n
if a_i > max
max <- a_i
output maxContext
StackExchange Computer Science Q#84207, answer score: 38
Revisions (0)
No revisions yet.