What should be the time complexity of the solution?


#1

What should be the time complexity of the solution?


#2

By my Binary Search solution, the time complexity is O(N logM), where N is the input array size and M is the maximum value in the input array. It only requires O(1) extra memory.


#3

it cant be sorted how come binary search huh?


#4

You do binary search on the answer, not the array. Google for “binary search the answer”.
There is another O(N log K) time complexity with O(k) space though. Kind of trade off between the O(1) space solution one.


#5

It is getting accepted in O(NlogN).


#7

If you prefer Quick sort to sort the entire array and find kth place element then it will take O(nlogn) time and if you follow Randomized QuickSelect algo then time complexity will be O(n)


#8

thanks mate really i good approach. Before reading your comment i thought it was impossible to do this.