I came across a question which I want an O(n) solution. The Question goes like
n=3 a=[4,2,1]
you have to build an array from the given array like this
[(4-4),(4-2),(4-1),(2-4),(2-2),(2-1),(1-4),(1-2),(1-1)]
which results as [0,2,3,2,0,1,3,1,0]
we have to find the kth largest element from the array with which we built.
For example the 4th largest element in [0,2,3,2,0,1,3,1,0] is 1.
Please help me find an optimal solution other than brute force one