Find the k'th Largest or Smallest Element of an Array: From Sorting To Heaps To Partitioning
Vložit
- čas přidán 24. 07. 2024
- Code & Problem Statement @ backtobackswe.com/platform/co...
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given an array and k, find the k'th largest element as efficiently as possible. Return the actual value of the k'th largest item.
I got this question in my final round of Facebook internship interviews...this is before I knew how to solve recurrences and analyze algorithms, etc...I fucked it up but who cares...I talked for so long and thought the optimal solution was log(n)...but I was really wrong.
Approaches
Sort: O(n*log(n))
Use A Min-Heap: O(n*log(k))
Remember QuickSort...how does it work...what does it fundamentally do...partition
The kth largest element will be at index n - k
Ex:
arr = [ 3, 2, 1, 5, 6, 4 ]
k = 2
The first largest element should be at the last index ... index 5 ... (6) - (1) = 5
The 2nd largest element should be at index (6) - (2) = 4
The n'th largest element should be at the first index ... index 0 ... (6) - (6) = 0
So...
finalPivotPosition == n - k ... The pivot is the k'th largest element
finalPivotPosition greater than n - k ... k'th largest must be in the left partition
finalPivotPosition less than n - k ... k'th largest must be in the right partition
We an pick a pivot however we want but random is best since we have a equal likelihood to pick any element.
The worst case is O(n²) but the likelihood this can happen goes down exponentially because it can only happen if the greatest or least item is chosen as a pivot repeatedly.
Complexities
Time: O(n)
On average we will be splitting the input in half leading to a recurrence of T(n) = T(n/2) + (n - 1)
If we solve for these exact amount of comparisons we see that we stay to the order of linear time.
Space: O(1)
Everything is done in-place.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is question 12.8 in the fantastic book "Elements of Programming Interviews". - Věda a technologie
Good day. I don't ever comment. However, I just wanted to say that all your videos are really helpful to both me and many others. I respect the level of time and effort you put into these video and how many people you are helping. What most tutors/lecturers don't understand is that even you help that ONE child at the back of the class, they might just end up being able to build the next big startup. This being just because of the extra effort people like you put. Of course the material is NOT easy. However, I respect and thank you for both me and many others who are really struggling or just want enrichment. So hopefully you can keep it up and just know that there is at least someone who benefits from your effort (probably many though). Channels like these are hard to come by. So please keep up the good work. You will never know who it may help!
"even you help that ONE child at the back of the class" I resonate with that the most. The problem with lectures is that it is always tens of people anywhere in the classroom that are confused but don't speak up because a lecture is a hard environment to be a real, inquisitive, student in. (this is why whenever I get a youtube comment I try to say..."keep asking questions" because if a student is afraid to ask...they lose the very curiosity that makes a great lesson...you know that quote....'the teacher and the student make the teaching' or something like that)
Thank you for your comment. It is a lot of work and every week I have to tell myself to keep doing this (but I mean...I want to make it sustainable eventually with products I'm building right now, etc...at that point I won't need motivation because this will hopefully be a sustaining business)
This comment served as my weekly energy renewal :)
I6
As the student in the back, thank you. I think it’s videos like these that really make me want to also help students out since we’ve all been there. I feel a great level of gratitude
"We're doing more work than we need to " that is a very clever way to think about a solution's quality while solving a problem.
yeah
Huge respect to this guy. The way he phrased his sentences, like " We are doing more work than we need to" , these will help you and move you in the direction of optimizing your solution. Thanks for the videos my dude.
thanks - this guy
@@BackToBackSWE haha
I don't usually comment but this is the best explanation for quick select algorithm ever ! All of your videos are amazing and easier to understand than many other resources online. Thank you so much !!
thanks
Man, you're like a brother to me. I've learnt so much from your simple videos that I couldn't from my college years. Thanks a lot. I am considering binge watching your whole channel.
Haha, nice to hear, I mean, as humans we are all siblings. Anyway, glad they are helping you. - Ben
It's awesome that you showed the entire thought process, including the well-worth detour of heap solution. Also the time analysis part is eye-opening. Unlike the merge sort, we avoided the sorting in partitions, leaving only the n/2^i as the leading term in big O, which adds up to O(n). Thanks for going into all the details, it really pays off as a better learning outcome!
Among other CZcamsrs, your way of explaining the thought process besides logic (which other coding channels usually lack) is right at the top.
Awesome content.
Thank you good sir!
Great Video. The way you walked us through the problem and ended up at the average linear time solution was brilliant. Appreciate you taking time out to make such videos.
sure
Check out the free DSA Mini-Course 👉backtobackswe.com/five-day
Table of Contents:
Shameless Self Promotion & Useless Talking 0:00 - 0:45
The Problem Introduction 0:45 - 2:20
Approach #1: Just Sort The Array & Count K Back 2:20 - 3:50
Approach #2: Heap Based Approach 3:50 - 5:02
Min Heap Approach Walkthrough 5:02 - 7:41
Seeing How We Can Improve Further 7:41 - 9:51
We Realize What We Need To Do 9:51 - 10:43
Where Will The k'th Largest Element End Up? 10:43 - 13:19
Approach #3: Walking Through A Partition Step 13:19 - 16:58
Approach #3: The Deep Deep Deep Understanding 16:58 - 20:43
Analysis: Looking At The Recurrence 20:43 - 24:53
Analysis: Solving The Recurrence 24:53 - 27:14
Analysis: Our Final Result 27:14 - 28:11
Wrap Up (and space complexity) 28:11 - 29:54
Comments:
27:35 -> What we just solved is the recurrence for the Best Case where we choose a pivot that is the median in the partitioning space and the resulting input gets split perfectly in half. This is not a rigorous Average Case analysis but it approximates what will generally happen very well so that we can see why the asymptotic complexity will be O(n). (and it is also Ω(n)...so therefore the runtime is Ө(n)).
The code for this problem is in the description. Fully commented for teaching purposes.
A big thank you for this video. Also, could you please tell me good resources from where I could practice time complexities of recurrance relations
sure and you can just google stuff, no specific resource
@@BackToBackSWE I don't see the code in the description, I've tried to make this algo in code myself but it's not working out.
@@mriKsuN i just saw some line explaining the code not the actual code.
@@shyammuppidi2092 github.com/bephrem1/backtobackswe/blob/master/Sorting%2C%20Searching%2C%20%26%20Heaps/KthLargestElement/KthLargestElement.java
One of your best videos when it comes to an explanation. It's clearly visible that you have put your heart and soul while explaining deeper logic. What an honest effort, may you get all the success you wish for!
Yeah haha, this is fire. Thanks haha
Your understanding of the fundamental concepts is phenomenal and rare to find.
thanks
I really like how in-depth your videos are. Comparing to many other channels where people either go lightning fast or just gloss over the details, your step by step handholding and the big O analysis rock! I know what is next on my bingewatch list. ;-)
You're awesome!! Appreciate all your efforts that you put in to explain a problem, the thought process, solution, time complexity analysis. Huge respect for you!
thanks and sure and thx
Ben, it's amazing the amount of knowledge you have on CS fundamentals, I am learning a lot, thank you!
haha, thanks
the best channel for preparing coding interview
I know. Give me 2 more years. CZcams is 😴😴😴 on me.
Facts.
@@colorfulcodes hahaha
11:50 is literal gold, I never thought of representing K and N in that way visually. It makes accessing K and thinking about how to index into it manageable. Freaking awesome.
thanks haha, I don't remember what I say in like all my videos
@@BackToBackSWE Again appreciate this video, I swear I was struggling all day to try to understand this algorithm, and I watched your video, then your quicksort video, and then whiteboarded some examples on paper and finally got it. Thanks a ton.
@@SocajowaRS nice
cuz u noob
I just went through just once. Its been looong that i dont even remember what is quick sort. but with this video i just understood quick sort as well as how and where to apply quick sort. Good work buddy.
Hey man, you have the best algo + ds explanations and walkthroughs on the entire internet. Bar none. Was a wahoo but go terps lol.
thanks! yeah uva is perty
You know that feeling when it just clicks. You and NeetCode always get me there. Thanks for all your hard work
Keep it up man, I really think this channel will be well known very soon.
working on it
Thanks from China.I liked several videos of you since I met your channel yesterday. Really appreciate the details and the way you present.
This is the best explanation of quick select I have found online. Thank you for this video.
I have watched so many videos till now and still you are the best. Man you make these concepts feel so easy and your videos are damn amazing and very easy to understand. Thank you so much and also its available for free loved them man
I am never going to forget quicksort because you taught me how to actually use it. Beautiful explanation
ye
Benyam, you are a gem of teacher and person. This is by far the best way to make me think. Thanking is not enough but thank you. Specially for keeping it for free, many of us could not have stumbled upon this or be able to afford this level of video.
Please do keep up and more love from India.
Btw, the donation option doesn't work in India yet and i'm sure your fans like me in India would like to contribute in some capacity.
Reading up on quickselect thru leetcode solutions wasn’t effective at all for me but this video is simply brilliant. Realizing that we don’t have to perfectly sort EVERY integer is the first thought that tells us a heap is overkill, then using a pivot from quicksort to partially sort ONLY the half of the array we care about (and split the array further with each pivot) is the second thought that makes sorting FASTER possible. Really going into depth on how we conceptualize quick Select is what’s more valuable than the code itself. Explaining it this way is sure to blow the interviewer’s mind as it shows the raw thought process being formed from simple observations.
yuh
Ben you are a genius. Thank you so much you made this problem so easy!!!. Appreciate you for your efforts and time :D
Love your channel!!
I seem smart but I'm not. And nice - sure - and thanks!
Congratulations your final dialogue of happiness in everyone's life earned you a subscribe. Aight imma make my chemistry major roommate subscribe too.
wut
Amazing explanation!This has really helped me understand how partitioning works , and the details that i have missed .
great to hear
Huge respect to this guy! Thanks a lot, these videos are amazing!
I like the way you walked through your thought process.
Excellent vids. Good sense of humor. Clear explanations. Two things: I have seen the partitioning solution *after* the date you posted this, but have never come across it before -- or seen references in videos prior. Is this your solution? Incredible! The other thing: when referring to a "good" pivot, you are of course thinking quicksort. This is different. If I have a million item array and I want the 20th largest, the best first pivot should be just smaller than the 20th largest. You *read* a million elements, and if they're larger, you *swap* them. So if your pivot is (for instance) 999900, you only do the swap like 100 times. This is good for speed. And then your next search is finding your k-spot in a list of 100 items. See how much faster that goes? Instead of n + n/2 + n/4 ... it's more like n+200. YMMV Hope you like this twist HALF as much as I enjoyed discovering "your" partitioning solution. It was a delight! (there *is* a general case and there *is* a quick pivot-finding algo)
Mannn you are the kinggg❤️❤️
A day before the exam on data structures i saw this video.. N this question was on the exam 🙂🙂
hahaha nice
Its amazing how easy your explanations are
Keep Making Videos please....a humble request from your regular student..you are truly a great teacher
ok, say no more, I got u
you are too good Ben! your videos are very helpful. please keep making them.
haha ok, I will, as long as I'm a live
Makes such great sense... you do amazing work. Thanks... Finding the big of the work.. I still totally suck at that .... thanks for doing great work for us all
This is very good, man! Very good!! Thanks for teaching!!!!
haha thanks
No one can ever match your style of explanation. Super !
thanks
Dude, your explanation! Absolute magic. Better than the paid courses!
thanks
You have the best explanations I have ever seen. Definitely earned a sub.
welcome, you are loved
Thank you for all videos ! Very understanble !
Glad you like them!
14:00 you choose first element as pivot and swap it to the last , rather than doing this directly choose the last value as pivot.
Any number can be the pivot? Why the last?
@@BackToBackSWE yes any element can be the pivot ..But since we have to make a search space from L to R , so its better to choose last element, just an opinion:)
Your explanations are so easy to understand.Thanks a lot🙌🙌
studying for my algos final rn thank u so much
love your content man, kudos to you
I appreciate that!
I officially love you and I love this channel. You save me!!!!
great
Thank you for your videos! You're an awesome for making them.
thx
you are great!
keep the good work.
Greetings from Mexico.
This partitioning is linear time only when we can ensure the pivot is proper right? but when we measure an algorithm's time complexity, do we not go by the worst case? And when we choose the pivot to be the worst(largest element), we would lose the entire left partition and thus losing the actual answer too in some cases right? Please clarify if am I missing something
Great video!
So much effort that you've put into it!
ye, change da world, my final message
Can it be a possible solution that we do a heap sort using a max heap and stop after kth iteration to get the kth largest element?
BRO... you also need to share your upper push body workout. You are in great shape
hahahahaha
Always love your enthusiastic when explaining, down to the smallest detail. Keep up the good work. I wish i've chosen CS major
thanks & u can always do whatever. life is long in years.
After watching so many videos this video helped thanks a lot brother
sure
Clear Explanation... Thanks a lot for taking the time and effort to make these videos. Good Vibes and Blessings from CS Students.
thansk and ye
Thank you so much for such in depth explaination! The video content is gold! Love and support from India!😀
This man is better than 90% of my cs department at explaining these concepts
as a math lover I really enjoy your explanations, thanks man
Could you provide the order that we should follow to watch those videos? Because the beginning of the video shows that you've already covered the sorting methods, but it is the 2nd video in this "Sorting, Searching, and Heaps" playlist, so I got a bit confused by which one to start. Thanks for teaching, and your videos are really easy to understand and get to the point!
Hey, I'm rapid fire responding to comments (I got behind 250 after 2 weeks) I'd answer this but in a hurry, so sorry
I recommend no specific order, just work on what you are weak on
...at one point in time I could answer everything ugh - ben
or can we do this way use max heap for kth largest element and popout the max element k times then well have the kth largest value?
Very good teaching style. Thanks for the tutorial!
sure
@25:30 Can anyone explain why is the summation on the right is simplified to lg(n)and not lg(n)-1? Where did the minus one go?
Can you please make another video for the same question using "median of median" approach which has linear time for worst case as well.
this was an awesome tutorial man ! thanks !
thanks and sure
I also never ever comment videos, and I never ever subscribe, specially when somebody asks me to subscribe. Nevertheless, your videos show a couple things:
1) A great amount of effort to condense the information to what's truly needed
2) An intuitive explanation
3) Barely any overhead in the video itself
4) Charisma when teaching
5) The importance of sharing knowledge
For this I am very thankful, subscribed and if you open a Patreon or alike, willing to contribute to your cause. Kudos.
thanks for the detailed analysis haha
I am a programming newbie and I am learning a lot from your channels. Just one observation, from your python code, where there is a while loop (while left
Awesome Explanation 🙏🏻 Thanks a lot
sure
I think you could have just said, in the complexity analysis part, that the sum from i = 0 to something of (1/2)^i, is strictly less than the sum from i=0 to infinity of (1/2)^i = 2, and so you end up with the answer being less than 2n - log(n), therefore it is linear complexity.
Your videos are awesome dude, keep it up.
thx and ok
This is my 2nd or 3rd comment ever on CZcams. But all I wanna say is: "I wish there was a provision of giving more than one like". Thanks a lot.
Hahahahhahaha, this vid was fire, not sure if I can drop more like it. Let's see haha
One question on the heap solution: are we supposed to implement the heap bottom to top before solving problems in real interview (in case that's the solution we come up with)? Just thinking it'd be quite hard to do heavy and bug-free implementations under gunpoint.
would heapifying the entire array then extracting min/max k times be faster or slower than the heap approach you gave?
O(n) + O(klogn)
Not sure to be honest. O(k*lg(n)) vs. O(n*lg(k)) would have very similar tail behaviors since they are basically the same function (just with the n and k swapped).
We could solve for the exact average case for that approach and then compare them using the concrete amounts...that would be the best and most sure thing to do.
But yeah, I'm not 100% on that.
Man!!! you are amazing :) thank you so much
sure
thanks a lot. one question only. You say "the code is in the description". I have searched in the Description - there is neither code or link to it. So where to find the code ?
That was beautiful, thanks!!!
sure!
this is a gem, thanks for share it
sure
Man! You the man!
thx
for choosing the pivot int choosenPivotIndex = rand.nextInt(right - left + 1) this should be enough to pick a random index correct, why we need to add left for this. Please help me to understand
to compute the range of numbers?
Love your channel and effort.
thanks
can you please let me know how this work if numbers are not in seq or random. I think it fails ..please correct me if I am wrong.
The numbers can be random
This was the first question interviewer asked me 🥳
nice
Thanks !! Can you do topological sort (leetcode course schedule problem)
sure and probably not
Great job man.. 🔥
Great Explanation, thanks
sure
I am puzzled! Just by using Priority Blocking Queue, We can solve it in 0(n) Complexity, right? Why to rely on the Re-implementation of the QuickSort algorithm again? Please correct me if I am wrong !
public int findKthLargest(int[] nums, int k) {
// TODO Auto-generated method stub
PriorityBlockingQueue pq = new PriorityBlockingQueue();
for (int n : nums) {
pq.add(n);
if (pq.size() > k) {
pq.remove();
}
}
return pq.remove();
}
That structure has operations underneath that likely add complexity? Not sure never used it
@@BackToBackSWE PriorityBlockingQueue solves the problem in O(n)! But using Quick select is even more efficient, I am able to increase the performance of my code more than 80 percent!! Cool! Kudos to your efforts !!
This channel is fuuuuuckin amazing man. Sorry for cursing but I had to.
thanks and ur good
Thanks bro, That was really helpful.
sure
Keep it up!!
I read all your reply to the public comments that are brilliant& interesting.
And I wait for your reply...!!
lol most are basic
After you eliminate the left side of the search space, do you sort the remaining right side?
You call the recursive subroutine on the right side.
So... is this quick sort but we are discarding the half not containing the outcome every time?
Why do we get largest from min heap? The root of min heap is smallest, so isn't it more beneficial to use a max heap?
I see your comments all over leetcode lol, great vid.
hahaha yeah...those were the days..
thanks for your video
Could you please make a video on - finding kth smallest element in a row wise and column wise sorted array? How to extend the heaps solution to that question ? (I saw your - Search A 2D Sorted Matrix video and it was awesome.. I wanted to know how heaps can be used in that scenario)
Thanks :)
I can't due to time constraints sadly
Awesome content as always! Go Terps!
hey.
Great, thank you very much
sure
Buddy, I think you have calculated the average case time complexity. What happens if pivot doesn't manages to split the array in halves, and the pivot happens to be one of the extremes. In that case, the worst case time complexity would be T(n)=T(n-1)+(n-1), which evaluates to O(n^2), which is even worse than heap-based approach. But anyways, I liked the way you think.
What was the recurrence I solved?
You solved for the best case i.e., T(n)=T(n/2)+(n-1)
@@growingwithtech Ah, yeah, rewatched it, yes the worst case is O(n^2).
I analyzed the best case (where we assume a 50/50 split), and it follows near the same reasoning as the average case (where we assume a 75/25 split) which also bounds to O(n).
More on the average case: web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/09/Small09.pdf
Thanks for the question
Exactly!! Thanks for the clarification
The explaination was too simple but the complexity analysis was little complicated to understand. However the code implementation was so easy t understand that this problem looks easy for me. Thanks a lot :)
cool
Great video and any plan for box stacking DP ?
thanks and no