Kth largest element in an array | Kth smallest element in an array

I wish the explanation included details on max and minheaps...

java solution:
class Solution {
public int lastStoneWeight(int[] stones) {
PriorityQueue<Integer> pq=new PriorityQueue<>(Collections.reverseOrder());
for(int i:stones){
pq.add(i);
}
while(pq.size()>1){
int f=pq.poll();
int s=pq.poll();
int diff=Math.abs(f-s);
if(diff>=0){
pq.add(diff);
}
}
return pq.poll();
}
}

I have a question what if we use bubble sort. But in our program will be like this

Pseudocode #

Store first array elem : int x = arr[0];
Now loop till n-1
Inside the loop check if arr[n] >= x;

Do we get O(n)?
Which is better that O(nlogn)

I think insertion in a heap also takes nlogn time

Thank you for the lecture

Hey brother cant we just sort the array and then giv the index for example
we can use sort(arr,arr+n);
and then return arr[k-1]

does building heap takes o(n) time?..i think its o(nlogn)!

We can also use priority queue (maximum) such that will pop elements upto k-1 and simply print the top

The first approch doesn't work if there's duplicate values in array.

how is buildig a heap takes n? i mean should not it be O(n * logn)? i.e.. overall complexity of this approach should be O(n * log n + k * log n) = O((n+k)log n)

easy c++ solution using priority queue
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int>pq(nums.begin(), nums.end());


int ans;


for(int i=1; i<=k; i++){
int a = pq.top();
pq.pop();
if(i==k){
ans = a;
}
}

return ans;
}
};

building heap is not O(N), its Nlog(N).
hence TC will be nlogn + klogn

How the avg. time is O(n) for Quick select ? It should be O(kN)

What if there is duplicate element in an array

using max heap or min heap you get NlogK time complexity

Well you can use Bouble sort to get nth largest no. Because as we know that on each iteration bouble sort sorts the largest no to the most right and others sort before it. So we have to iterate nth time and then at position array.length - nth_largest_ we have the desired no and this algo will give us nth_no*n which will be considered n and constant will droped. And for nths smallest no we can we same logic

Can we use a set for this? Set has time complexity of logn, isn't it?