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".
Watch video Find the k'th Largest or Smallest Element of an Array: From Sorting To Heaps To Partitioning online without registration, duration hours minute second in high quality. This video was added by user Back To Back SWE 19 April 2019, don't forget to share it with your friends and acquaintances, it has been viewed on our site 271,731 once and liked it 6.1 thousand people.