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

This video lecture explains 3 methods to find out the kth smallest or kth largest element from a given array. The first method is based on sorting, the second method is based on heap (both min heap and max heap) and the third method is based on quickselect algorithm. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

[techdoseu]

🟣 JOIN our 𝐋𝐈𝐕𝐄 𝐢𝐧𝐭𝐞𝐫𝐯𝐢𝐞𝐰 𝐭𝐫𝐚𝐢𝐧𝐢𝐧𝐠 𝐩𝐫𝐨𝐠𝐫𝐚𝐦 through whatsapp query: [phone]

[ibuykx]

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)

[suchitragiri]

Really! very clear and easy to grasp explanation !

[finster]

6:10 for min heap time complexity should be O(N + (N-K+1)logN)) . Isn't ii?? @TECHDOSE

[willturner]

We can also optimize it with quick sort

[saunaknandi]

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

[urrahman]

5:56, shouldn't it be n-k+1 * log(n)? couldnt understand

[pha]

Why can't we make a heap of size k and run through all the elements? The min would the top element in the end.

[saikirank]

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

[gouravkrroy]

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

[ankuradhey]

You are maintaining a heap of n elements. But it can be used heap with k elements. In this way complexity can be O( n + n log k)

[abhishekranjan]

sir, Time complexity using min heap : O(n)+(n-k+1)log(n-k+1) is right or O(n)+(n-k+1)log k ??

[zeeshanhasankhan]

What if there is duplicate element in an array

[nayanjain]

There is O(N) approach also, I was waiting for that entire video, at least mention complexity in the video title.

[avinashdharme]

0:39 third largest would be 6, If I m not wrong.

*Rest, very good explanation!!!*

[AjayGautam-ikdm]

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

[crackthecode]

Sir, please add one video..find the median of sorted matrix, pls sir plsss

[MuhammadWaseem-mjge]

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

[soumayanmajumder]

Please make a video on resume building and please show us your CV/ resume for Samsung r&d and tcs digital.
It will help us lot to get a direction.

[prashantsingh]

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)