To find the kth largest element in an array

#1

i saw a solution that used min heap of k elements to solve this question in o(Nlogk).
shouldnt i directly create a max heap and pop out k times , that will take o(N + klogN).

which one is better and why?

#2

Hey @niketagarwal10
Assuming k can be N in worst case
So in first solution time will be 2*NlogN =O(NlogN) and space is O(N)
and in 2nd case time will be N+NlogN =O(NlogN) and space is O(N)
So both are equal for k=N

Now assuming k less than N
So in first soln O(Nlogk) space is O(k)
In 2nd soln O(N+klogN) space is O(n)

So here lets assume k=N/10 and N=10^10 So in 2nd case its 2*(10^10) and 1st case its 9*10^10
So according to me Time complexity of 2nd soln is little better but 1st solution is more space optimixed.