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

Code & Problem Statement @ https://backtobackswe.com/platform/co...

Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://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".