Find the k th Smallest/Largest Element | Quick Select Algorithm | Optimizing Quick Sort

Finding Kth largest and smallest element of an array in an Optimized way is common software coding interview question asked in amazon, google, facebook, microsoft coding interview round.
Here you are given an array of number and an integer K, you need to find the Kth smallest number in the array.
There are multiple ways:
1) Brute Force way: Sort the array and the return the kth element of array, time complexity for this is O(nlogn)
2) use extra space and go for min heap, space complexity for this is o(n) and time is O(nlogk)
3) Optimized solution : Use Quick select, which is an optimization on top of quick sort. This algorithm in it's worst case will give o(n2) time complexity but in average case it will run with time complexity of O(n).
In this video I have described how quick select works and implemented it as well. You can get the code from below mentioned github link.
subscribe to the channel to get more content on :
1) job interview
2) softwares
3) systems design
4) cracking the coding interview
5) algorithms
6) system design interview questions
7) object oriented programming concepts
8) software design patterns
You can buy us a coffee at : www.buymeacoff...
system design: • System Design | Distri...
DS for beginners: • Arrays Data Structures...
leetcode solutions: • Leetcode 84 | Largest ...
github: github.com/The...
facebook group : / 741317603336313
twitter: / granthtech

[@abhimanyu6215]

Struggling to find a good explanationary video but at last came here and completely understand this problem. Thanks a lot sir! 😊

[@mohammadyahya78]

Thank you very much. None has explained this problem better than you so far.

[@TheTechGranth]

Glad it was helpful. Do like and share and subscribe to the channel

[@quocvu961]

From researching priority_queues, I think your time complexity for method 2 (PQ) might be incorrect.
At least C++ priority_queue use sift_down() during buildHeap, which will make the creation of a PQ from an array O(n). See Heap constructor from array.
Select ascending vs descending for smallest vs largest respectively.
Loop through pq to pop elements until you reach k-1 and pq.pop() should be the kth smallest/largest element.
In total, this algorithm should provide at max O(n) + O(k), where O(n) > O(k) -> so the time complexity should be O(n).
Or am I misunderstanding something?

[@mohammedshahbaz623]

I went for various yt videos, but this was the one which cleared my concept. thankyou

[@TheTechGranth]

Glad it was helpful. Do like and subscribe and share with others 🙂

[@mohammedshahbaz623]

@@TheTechGranth hiii,
gfg is not accepting the approach, as only 156/166 testcases are running. it is suggesting something like random pivot concept. Can you please elaborate?

[@SumitSharma-do2uc]

@@mohammedshahbaz623 instead of picking high as pivot element....use random() inbuilt function to pick pivot element

[@ravis8099]

here when pivotPoint < k-1, why are you searching in the right sub-array for the kth smallest element again? If pivotPoint is < k-1, then you only have to search the index of the (k-1-(pivotPoint))th in the right sub array, isn't it?

[@RajeshSharmaIndia]

Thanks , you made it simple and easy.

[@SaifMohamed-de8uo]

when i put diffrent values for low and high(get k smallest element in a range of the array) the program die and i dont know the reason

[@harshalkallurkar9160]

Thank you very much..illustration was really helpful!!

[@TheTechGranth]

Glad it was helpful. Do like and subscribe and share with your friends 🙂

[@AdityaDhage-1603]

Simple and easy explananation.

[@sam_s3344]

So well explanined. Thank youu!
Do you have code for this anywhere?

[@TheTechGranth]

My git link is there in description. You can get the complete code from there.

[@sam_s3344]

@@TheTechGranth oh will check this out thank you so much!

[@sam_s3344]

@@TheTechGranth and another doubt. If we have a particular question to request your video on, can we comment it anywhere? Do you take such requests?

[@TheTechGranth]

@@sam_s3344 you can comment here or send mail to our id

[@sam_s3344]

@@TheTechGranth Oh this is going to be very helpful. Thanks a bunch!

[@AkashKumar-tp8vk]

great explanation