|
Given an array, if all the elements are distinct, can we find the count of elements which are lesser than an element and present to the left of that element in linear time if we have to do it for every element. I know this can be solved in |
|||
|
|
|
You cannot do it in linear time using only comparisons. If you could, then you could do it for the array and its reverse in $O(n)$ and then for each element determine in $O(1)$ its position in the sorting of the array. This gives a comparison-based linear time sorting algorithm, which we know cannot exist. You have to tell us more about the domain of the elements in the input array if you want to get an $o(n \log n)$ algorithm. For example, do you have a constant upper bound on the value of the maximum element? |
|||||
|
|
asked |
yesterday |
|
viewed |
89 times |
|
active |
