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

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

Наука