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

Title:

Description:

Code & Problem Statement @ https://b2bswe.co/find-the-kth-largest-or-smallest-element

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
Subscribe To Live Tech Offers: https://offerfeed.io
Join Our Coaching Service: https://backtobackswe.com/coaching

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: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: https://www.youtube.com/user/tusharroy2525

GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: https://www.youtube.com/user/VSympathyV

Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

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

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

YouTube url:	https://www.youtube.com/watch?v=hGK_5n81drs
Created:	8. 3. 2021 13:02:39

CaptionsMaker.com

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