Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python

0:00 - Read the problem
3:39 - Drawing Explanation
11:40 - Time Complexity
13:25 - Coding Explanation

leetcode 215

#quick #select #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[samrj]

This now exceeds the time limit due to the last test case added by leetcode.

[cqymDoerj]

To me, this is one of the best leetcode solution channels I have found so far!

[almasabdrazak]

I usually don't even look at your code because explanation is clear enough to implement it by my own, thanks

[qspec]

Like others have pointed out, this will time out on a test in leetcode, though the solution is pretty quick and easy.

Problem: if you pick a static pivot, it has a possible worst case. To fix this, instead of picking the rightmost pivot, just pick a random pivot between l and r and then swap that with the right most pivot. This significantly decreases the odds of catching the worst case time complexity.

[prempeacefulchannel]

I am preparing for my coding interview and your tutorials are helping a lot! Thanks!

[sipwhitemocha]

Clear explanation, visuals, codes, and also not condescending at all.

Thank you for your videos

[MinhNguyen-lzpg]

Awesome explanation! I agree that if we understand the quicksort algorithm first, the quick selection approach will be much more intuitive. Basically, in quicksort partition, we know that the "pivot" is a point where the left-side number(s) are less than the pivot and the right-side number(s) are larger than the pivot. We keep recursively running until the pivot aligns with the length - kth position. This would definitely challenging if I have not review quicksort :)

[surters]

The choice of your P might be the reason it runs so badly, if the array is already sorted it will run in O(N^2), better select a random index.

[jambajuice]

for those who use c++:


if u push elements one by one into the priority queue it will take nlog(n) time . coz pushing one element takes logn time

an efficient way to do this is :

priority_queue<int> pq(arr, arr + N);

it takes only o(n) time

[geekydanish]

max heap solution
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = []
for num in nums:
heapq.heappush(heap, -num)
while k > 0:
res = heapq.heappop(heap)
k -=1
return -res

[ehsanganjidoost]

for heap solution, O(n log k) since you have to keep a heap of size k.

[snehamd]

Your videos get etched in my brain forever! So clean, very systematic and easy to follow.. Thank you very much for such great content!

[pekarna]

Alternative:
1) With each number, insert it to a minheap; if the size is over K, remove the minimal (aka. "pop").
2) get all items in the heap and return the largest.

Another alternative: The array needs not to be sorted fully -> QuickSelect algorithm.

[patrickcunningham]

Great video! Many people have mentioned the new test case LeetCode has implemented, which causes quickSelect to time out. In Python, even changing the algorithm to use a random pointer instead of the rightmost element did not fix the issue. The max heap solution still works with the new test cases. Love your videos!

[chairuizhong]

Thank you so much for this video, i got this question for my meta on site interview today.

[waiyipli]

Add these two lines at the top of the recursive function can improve run time from over 2500ms to <100ms:

rand = random.randint(l, r)
nums[rand], nums[r] = nums[r], nums[rand]

[tttrrrrr]

It's a pretty common case to have to work on data that is pre-sorted or near pre-sorted, so this implementation with using the last element as the pivot isn't a good choice. Many people have suggested picking a random element and switching it for the last element, but for arrays where every element has the same value that still leaves the input array sorted and still takes quadratic time. An additional improvement is to keep track of the last index < pivot and use that for the left window, instead of p-1. This eliminates processing duplicates of the pivot repeatedly. E.g.:

class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
n = len(nums)
k = n - k

def quickselect(l, r):
pivotIndex = random.randint(l, r)
nums[pivotIndex], nums[r] = nums[r], nums[pivotIndex]

pivot = nums[r]
p = l
lessEnd = -1
for i in range(l, r):
num = nums[i]
if num < pivot:
lessEnd = p
if num <= pivot:
nums[p], nums[i] = nums[i], nums[p]
p += 1

nums[p], nums[r] = nums[r], nums[p]

if k > p:
return quickselect(p+1, r)
elif k > lessEnd:
return nums[p]
else:
return quickselect(l, lessEnd)

return quickselect(0, n-1)

[rns]

As of today, 22/10/23 leet code is making this solution TLE. So probably they have made some changes either in test cases or in time limit. But it was worth to learn it.

[flavorfabs]

Might be worth reuploading this problem. A test case was added that causes this input to fail.

[shwethaks]

As always on of the best leetcode solutions explanations. You are absolutely the best.