Find the k'th Largest or Smallest Element of an Array: From Sorting To Heaps To Partitioning

[@anthonyesquire9830]

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!

[@BackToBackSWE]

"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 :)

[@damodarmahawar9748]

I6

[@Sarah-re7cg]

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

[@sourabhk2373]

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.

[@BackToBackSWE]

thanks - this guy

[@CodeSuccessChronicle]

@@BackToBackSWE haha

[@addiegupta]

"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.

[@BackToBackSWE]

yeah

[@sarojinigarapati95]

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 !!

[@BackToBackSWE]

thanks

[@vedantiyangar151]

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.

[@BackToBackSWE]

Haha, nice to hear, I mean, as humans we are all siblings. Anyway, glad they are helping you. - Ben

[@jiazhengguo5493]

the best channel for preparing coding interview

[@BackToBackSWE]

I know. Give me 2 more years. KZbin is 😴😴😴 on me.

[@colorfulcodes]

Facts.

[@BackToBackSWE]

@@colorfulcodes hahaha

[@kumarchandan9685]

Among other KZbinrs, 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!

[@gyrogojo]

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.

[@BackToBackSWE]

sure

[@roman_mf]

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. ;-)

[@amishagupta990]

Your understanding of the fundamental concepts is phenomenal and rare to find.

[@BackToBackSWE]

thanks

[@jameshuddle4712]

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)

[@helloiam2mas]

Hey man, you have the best algo + ds explanations and walkthroughs on the entire internet. Bar none. Was a wahoo but go terps lol.

[@BackToBackSWE]

thanks! yeah uva is perty

[@abhishek-n-chaudhary]

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!

[@BackToBackSWE]

Yeah haha, this is fire. Thanks haha

[@Pooja-xu4lp]

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.

[@kaustubhtrivedi5403]

Keep it up man, I really think this channel will be well known very soon.

[@BackToBackSWE]

working on it

[@SocajowaRS]

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.

[@BackToBackSWE]

thanks haha, I don't remember what I say in like all my videos

[@SocajowaRS]

@@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.

[@BackToBackSWE]

@@SocajowaRS nice

[@PoulJulle-wb9iu]

cuz u noob

[@johnvanschultz2297]

This is the best explanation of quick select I have found online. Thank you for this video.

[@brainstorming1369]

You know that feeling when it just clicks. You and NeetCode always get me there. Thanks for all your hard work

[@殷源源]

Thanks from China.I liked several videos of you since I met your channel yesterday. Really appreciate the details and the way you present.

[@rohanangajala548]

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?

[@TheSridharraj]

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.

[@francocamborda5076]

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.

[@BackToBackSWE]

thanks for the detailed analysis haha

[@chuckchen2851]

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!

[@adityasaxena3903]

Dude, your explanation! Absolute magic. Better than the paid courses!

[@BackToBackSWE]

thanks

[@ricardoorellana1168]

Ben, it's amazing the amount of knowledge you have on CS fundamentals, I am learning a lot, thank you!

[@BackToBackSWE]

haha, thanks

[@tapasu7514]

No one can ever match your style of explanation. Super !

[@BackToBackSWE]

thanks

[@navyakalra6774]

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!

[@BackToBackSWE]

thanks and sure and thx

[@shiveshbharti5442]

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

[@AJ3000_]

This man is better than 90% of my cs department at explaining these concepts

[@SinghFlex]

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.

[@BackToBackSWE]

Any number can be the pivot? Why the last?

[@SinghFlex]

@@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:)

[@ankuragarwal4014]

Keep Making Videos please....a humble request from your regular student..you are truly a great teacher

[@BackToBackSWE]

ok, say no more, I got u

[@roman_mf]

@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?

[@redherring27]

Congratulations your final dialogue of happiness in everyone's life earned you a subscribe. Aight imma make my chemistry major roommate subscribe too.

[@BackToBackSWE]

wut

[@OP-yw3ws]

Its amazing how easy your explanations are

[@advertronicssystems8377]

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

[@mr.mystiks9968]

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.

[@BackToBackSWE]

yuh

[@deepraj279]

I am never going to forget quicksort because you taught me how to actually use it. Beautiful explanation

[@BackToBackSWE]

ye

[@tedytedy8918]

Mannn you are the kinggg❤️❤️ A day before the exam on data structures i saw this video.. N this question was on the exam 🙂🙂

[@BackToBackSWE]

hahaha nice

[@footerrykim]

For partitioning, why input size cut in half every stage? Isn't Input size still adjusted to n-1 based on the pivot??

[@BackToBackSWE]

The pivot just defines the value we partition against. We split in half (in a best case) since that is most optimal and if a good pivot is choosen then that will happen.

[@footerrykim]

Back To Back SWE thx for quick reply. I was just making an assumption that the first pivot is the highest index and you keep searching towards to left partition..

[@qwarlockz8017]

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

[@adityasoni1207]

Huge respect to this guy! Thanks a lot, these videos are amazing!

[@Mrwiseguy101690]

You have the best explanations I have ever seen. Definitely earned a sub.

[@BackToBackSWE]

welcome, you are loved

[@nirajchowdhary7372]

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!!

[@BackToBackSWE]

I seem smart but I'm not. And nice - sure - and thanks!

[@stk1526]

Amazing explanation!This has really helped me understand how partitioning works , and the details that i have missed .

[@BackToBackSWE]

great to hear

[@ashutoshtiwari4398]

I like the way you walked through your thought process.

[@mubarakoyeyinka8520]

Thank you for all videos ! Very understanble !

[@BackToBackSWE]

Glad you like them!

[@DarshanSenTheComposer]

The distinction between: i. T(N) = T(N / 2) + O(N) ii. T(N) = *2* T(N / 2) + O(N) took me by surprise! _sigh_ stupid me I've been watching some of your lectures for a while. I've gotta say, you're a really good teacher. Keep up the good work! :)

[@BackToBackSWE]

Thanks. Yeah, former bounds to linear time, latter bounds to n*log(n)

[@wanderlustsiddhi]

Thank you so much for such in depth explaination! The video content is gold! Love and support from India!😀

[@badal1985]

you are too good Ben! your videos are very helpful. please keep making them.

[@BackToBackSWE]

haha ok, I will, as long as I'm a live

[@akankshasharma148]

Your explanations are so easy to understand.Thanks a lot🙌🙌

[@pushpendrasingh1819]

BRO... you also need to share your upper push body workout. You are in great shape

[@BackToBackSWE]

hahahahaha

[@bharathik6479]

Clear Explanation... Thanks a lot for taking the time and effort to make these videos. Good Vibes and Blessings from CS Students.

[@BackToBackSWE]

thansk and ye

[@5ko99]

Why there is no code in the description??? You said 5 times look that code, but where is it??

[@BackToBackSWE]

The repository is deprecated - we only maintain backtobackswe.com now.

[@ryoyamamoto6488]

This channel is fuuuuuckin amazing man. Sorry for cursing but I had to.

[@BackToBackSWE]

thanks and ur good

[@ivanleon6164]

you are great! keep the good work. Greetings from Mexico.

[@shubhampareek2378]

This is my 2nd or 3rd comment ever on KZbin. But all I wanna say is: "I wish there was a provision of giving more than one like". Thanks a lot.

[@BackToBackSWE]

Hahahahhahaha, this vid was fire, not sure if I can drop more like it. Let's see haha

[@chanish163]

U are awesome 👌 ...u are helping many students 🤜🤛

[@BackToBackSWE]

sure

[@TCErnesto]

as a math lover I really enjoy your explanations, thanks man

[@ojuskhanolkar7146]

I officially love you and I love this channel. You save me!!!!

[@BackToBackSWE]

great

[@factsheet4930]

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.

[@laksh5228]

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

[@Ambs_2024]

Very good teaching style. Thanks for the tutorial!

[@BackToBackSWE]

sure

[@BullishBuddy]

This is very good, man! Very good!! Thanks for teaching!!!!

[@BackToBackSWE]

haha thanks

[@lokeshs9449]

Keep it up!! I read all your reply to the public comments that are brilliant& interesting. And I wait for your reply...!!

[@BackToBackSWE]

lol most are basic

[@adityasrivastava8790]

Overpowered John!Great work;)

[@BackToBackSWE]

lol thx

[@adityasrivastava8790]

@@BackToBackSWE he he @johnlegend aka all of me! Gr8 work byddy

[@rupadosapati7628]

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

[@BackToBackSWE]

to compute the range of numbers?

[@NGBigfield]

Great video! So much effort that you've put into it!

[@BackToBackSWE]

ye, change da world, my final message

[@vansh2k6]

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 :)

[@BackToBackSWE]

cool

[@arunprakash1101]

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(); }

[@BackToBackSWE]

That structure has operations underneath that likely add complexity? Not sure never used it

[@arunprakash1101]

@@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 !!

[@Endlessvoidsutidos]

29 minutes of explanation multiple levels of complex thought involved both in math and computer science so much so that trying to explain it gets you kicked out of buildings .... LeetCode - Problem difficulty = Easy

[@BackToBackSWE]

lol

[@netopedia8733]

Awesome Explanation 🙏🏻 Thanks a lot

[@BackToBackSWE]

sure

[@Mardil]

Your videos are awesome dude, keep it up.

[@BackToBackSWE]

thx and ok

[@growingwithtech]

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.

[@BackToBackSWE]

What was the recurrence I solved?

[@growingwithtech]

You solved for the best case i.e., T(n)=T(n/2)+(n-1)

[@BackToBackSWE]

@@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

[@growingwithtech]

Exactly!! Thanks for the clarification

[@jyotisingh8183]

Hello sir, can you please tell me in heap approach for kth largest or Kth smallest element we used minheap or maxheap respectively, but on what bases we're removing smallest element from minheap and largest element from maxheap. I want to know the implementation like how we're comparing elements inside both heap so that we could remove smallest or largest element. Thank you.

[@BackToBackSWE]

Are you asking about how the heap works internally? Or at what capacity ejections happen?

[@jyotisingh8183]

@@BackToBackSWE Sir I mean that suppose for Kth largest Element we use Priority Queue and create a variable let's say large. Now I'll do large.add(arr); Next as you said to check if large.size ()>k then remove(); so how my large variable know which element is smallest? Same in the case of Kth smallest element how my variable know which element is largest so that we remove it.

[@BackToBackSWE]

@@jyotisingh8183 Ah, so the point is we remove the largest items so that only the k smallest are left over. If I have [1, 2, 3] and I want the 2 smallest, I will not want 3 to be in there. So when capacity hits 3, the largest item in the heap (3) leaves.

[@jyotisingh8183]

@@BackToBackSWE yeah sir I got the logic but how my variable know that I have 3 which is largest then remove it? There should be some condition which checks which is largest or smallest element is there in heap to remove it if heap.size()>k.

[@BackToBackSWE]

@@jyotisingh8183 It is a max heap so it is designed to keep the max element at the top to be removed.

[@kiwixuerong7383]

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!

[@BackToBackSWE]

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

[@rajivsarkar277]

One doubt ... if the array is sorted then only the kth largest element will be at 4th index at 18:29. without sorting how we came to a conclusion that the kth largest will be in the right half of pivot.

[@vanducnguyen346]

Always love your enthusiastic when explaining, down to the smallest detail. Keep up the good work. I wish i've chosen CS major

[@BackToBackSWE]

thanks & u can always do whatever. life is long in years.

[@colorfulcodes]

I see your comments all over leetcode lol, great vid.

[@BackToBackSWE]

hahaha yeah...those were the days..

[@chuckchen2851]

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.

[@andrews2945]

Your explanations and visuals are always on point, thanks again. No flame, just thought it was funny, but did you have a stroke @ 20:57 😆

[@BackToBackSWE]

sure, and my bad

[@DonTaldo]

love your content man, kudos to you

[@BackToBackSWE]

I appreciate that!

[@Messirobben047]

If I ever have to pay for coding interview preparation platform, it'd be back to back swe

[@gauravchaudhari3843]

your explanation skills on point how do you grown like that

[@BackToBackSWE]

not sure

[@tumul1474]

this was an awesome tutorial man ! thanks !

[@BackToBackSWE]

thanks and sure

[@sinaanyounus5449]

studying for my algos final rn thank u so much

[@evgeniifeygin1030]

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 ?

[@reneeliu6676]

No can't watch this after I'm drunk...I need to come back all fresh in the morning.

[@marlegagaming1274]

Lol🤣

[@BackToBackSWE]

haha

[@mohneeshgarg8706]

I code better after drinking, it keeps me focus..

[@JoseSagrero1]

Thank you for your videos! You're an awesome for making them.

[@BackToBackSWE]

thx

[@vikrant_462]

you are suberb, I always recommend your video to those who ask for help...

[@BackToBackSWE]

thx

[@sddhrtha]

Love your channel and effort.

[@BackToBackSWE]

thanks

[@PankajThakur-tc1dw]

@Back To Back SWE what do you think about what if you first build_heap in O(n) then rather than going for largest-MIN HEAP and smallest-MAX HEAP...... we can actually go largest-MAX HEAP and smallest-MIN HEAP delete k elements 1 by one from build_heap Array that way complexity will be klog(n).

[@ateamcoolboy5815]

The Greatest of All Time

[@BackToBackSWE]

ye

[@ShubhamPandey-un2sy]

next level vid bro

[@BackToBackSWE]

yes

[@dhyeyparekh4994]

very nice explanation of each and every point....

[@ankitgoyal8556]

This was the first question interviewer asked me 🥳

[@BackToBackSWE]

nice

[@minijain5936]

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?

[@jagriti2978]

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?

[@longuyen10119]

Awesome content as always! Go Terps!

[@BackToBackSWE]

hey.

[@Ankit-jn8ew]

The Like/Dislike ratio clearly shows how good your content is! Good luck in the future.

[@BackToBackSWE]

fascinating - thanks

[@MhZnSO4]

Man! You the man!

[@BackToBackSWE]

thx