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

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

++++++++++++++++++++++++++++++++++++++++++++++++++

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is question 12.8 in the fantastic book "Elements of Programming Interviews".

[anthonyesquire]

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!

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

[sourabhk]

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.

[sarojinigarapati]

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

[vedantiyangar]

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]

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.

[jiazhengguo]

the best channel for preparing coding interview

[amishagupta]

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

[kumarchandan]

Among other Youtubers, 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.

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

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

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

[helloiammas]

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

[mr.mystiks]

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.

[Pooja-xulp]

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.

[francocamborda]

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.

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

[ankuragarwal]

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

[adityasaxena]

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