Find the k'th Largest or Smallest Element: From Sorting To Heaps To Partitioning
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".
Видео Find the k'th Largest or Smallest Element: From Sorting To Heaps To Partitioning канала Back To Back SWE
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".
Видео Find the k'th Largest or Smallest Element: From Sorting To Heaps To Partitioning канала Back To Back SWE
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
![The Quicksort Sorting Algorithm: Pick A Pivot, Partition, & Recurse](https://i.ytimg.com/vi/uXBnyYuwPe8/default.jpg)
![How to Study So You Never Forget](https://i.ytimg.com/vi/8kKdmKrLbK0/default.jpg)
![Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python](https://i.ytimg.com/vi/XEmy13g1Qxc/default.jpg)
![Find The Second Largest Item - Heap & Tracking Approach (Beginner Big N Interview Question)](https://i.ytimg.com/vi/NheWPxGpoxQ/default.jpg)
![Total Occurrences Of K In A Sorted Array (Facebook Software Engineering Interview Question)](https://i.ytimg.com/vi/RlXtTF34nnE/default.jpg)
![](https://i.ytimg.com/vi/7yC1aN87Ydo/default.jpg)
![Implement A Binary Heap - An Efficient Implementation of The Priority Queue ADT (Abstract Data Type)](https://i.ytimg.com/vi/g9YK6sftDi0/default.jpg)
![10 Common Coding Interview Problems - Solved!](https://i.ytimg.com/vi/Peq4GCPNC5c/default.jpg)
![2.8.1 QuickSort Algorithm](https://i.ytimg.com/vi/7h1s2SojIRw/default.jpg)
![Reverse Polish Notation: Types of Mathematical Notations & Using A Stack To Solve RPN Expressions](https://i.ytimg.com/vi/qN8LPIcY6K4/default.jpg)
![Whatsapp System Design: Chat Messaging Systems for Interviews](https://i.ytimg.com/vi/vvhC64hQZMk/default.jpg)
![7 Common Mistakes in the Coding Interview (for Software Engineers)](https://i.ytimg.com/vi/pV7XIZnsbgM/default.jpg)
![Asymptotic Bounding 101: Big O, Big Omega, & Theta (Deeply Understanding Asymptotic Analysis)](https://i.ytimg.com/vi/0oDAlMwTrLo/default.jpg)
![How I Got An Internship @ Twitter](https://i.ytimg.com/vi/DUqwi-uUzWs/default.jpg)
![Knuth–Morris–Pratt (KMP) Pattern Matching Substring Search - First Occurrence Of Substring](https://i.ytimg.com/vi/BXCEFAzhxGY/default.jpg)
![Merge K Sorted Arrays - Min Heap Algorithm ("Merge K Sorted Lists" on LeetCode)](https://i.ytimg.com/vi/ptYUCjfNhJY/default.jpg)
![Google Systems Design Interview With An Ex-Googler](https://i.ytimg.com/vi/q0KGYwNbf-0/default.jpg)
![Interval Scheduling Maximization (Proof w/ Exchange Argument)](https://i.ytimg.com/vi/hVhOeaONg1Y/default.jpg)
![AVL Trees & Rotations (Self-Balancing Binary Search Trees)](https://i.ytimg.com/vi/vRwi_UcZGjU/default.jpg)
![Implement An LRU Cache - The LRU Cache Eviction Policy ("LRU Cache" on LeetCode)](https://i.ytimg.com/vi/S6IfqDXWa10/default.jpg)