Can anybody share a solution that is guaranteed to be O(n) in worst case (for any input), without using some existing hashing mechanism (cause they cannot guarantee O(1) access time in worst case)?
I cannot think of one, looking forward to your sharing.
@czzhang I think the proper answer (or at least the intended answer) for this problem is Radix Sort because we know the upper bound digits of any integer, so Radix Sort is practical with worst case O(n) guaranteed.
Any solution using set or map is not really worst case O(n), unless they allocate a bucket with the size of the whole integer space to prevent collision.
@ayuanx Thanks for your explanation. I am just curious on whether there is a solution based purely on comparison. For example, the k-th largest element can be found in O(n) time without using radix sort. But anyway, maybe the requirement of O(n) is a bit misleading.