Kth Largest Element in an Array - Leetcode 215 - Heaps (Python)

[@GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[@EverAfterBreak2]

The min heap solution explanation is so good, heaps can be used to solve a lot of “k or kth” problems

[@ew2430]

You have a talent for explaining, great video!

[@GregHogg]

Thank you very much 😊

[@thisisactuallyhilarious2575]

You actually don't need to negate your values. Instead of finding the kth largest number, you can find the (len(nums) - k + 1)th smallest number if that makes sense. For example if I had a list of numbers [1, 2, 3, 4, 5] and wanted to find the 2nd largest number which in this case is 4, I could technically find the (5-3+1) = 4th smallest number which is also 4.

[@GregHogg]

Interesting idea

[@hamadrehman853]

this is so good.

[@idannadi6451]

There is actually a better solution, which takes O(N + klog(k)) which is much better than O(Nlogk), but it takes O(k) space instead of O(1). It goes like this: 1. transform the given array into max heap. Call it A. 2. build a new empty max-heap (or rather priority queue) of size k + 1. Call it B a. in this heap we will keep all the candidate "next largest" items. b. every item in this heap will be tuple of value and index/pointer to that value in A. c. the heap propity will be according to the value field of the tuple 3.insert (A[0], 0) to B. now we will use this algorithm: for i in range(k-1): m = B.extractMax() # insert it's children, the only new candidates of the next largest number left_child_index = A.left_child(m[1]) right_child_index = A.right_child(m[1]) B.insert(tuple(A[left_child_index], left_child_index)) B.insert(tuple(A[right_child_index], right_child_index)) # end for # return the vaule of the k'th largest: return m[0] using this, when we "extract" form A, we dont fix it so we dont have to pay O(logn) each time, but rather by the log of size of B: O(log(1) + log(2) + log(3) +... + log(k)) < O(klogk) add the building of A max heap, ehih is O(n) we get O(n + klogk)

[@rohithbharathi3664]

import heapq class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: heapq.heapify(nums) for i in range(len(nums) - k): heapq.heappop(nums) return heapq.heappop(nums) this is just simple and similar to the maxheap sol .

[@KermitDominicano]

I didn't realize heapify only takes O(n) time! Good to know. I always assumed that it was O(nlogn)

[@Kashifalikhan]

Bro you are really amazing

[@egg2296]

Hey! Quick question: What tool do you use to explain the algorithm? Is it some whiteboard tool? PS: I am finding all your videos recently and they are very helpful in my preparation for my interviews. You deserve more reach!

[@aanwirawan]

in real interview, are we allowed to use heapq or we are expected to implement the heapify by ourselves?

[@venky3639]

😂 imagine asking to implement in Java or c++ 😢

[@venky3639]

Why is it log k at 8:20

[@rojo_pes75]

U are so good man🤟

[@na50r24]

Weird question If you use heapSort but k times, wouldn't that work too or does that count as sorting? It's strictly less than sorting the whole array and getting the kth largest element, since I only sort it k times with the outer loop rather than n. So it'd be O(k log n)

[@egg2296]

it does count as sorting... duh you are using heapSORT

[@na50r24]

@@egg2296 Sorting the whole array and then finding the largest element is different than sorting only as much as you need to get the kth largest element. Example: 1mil elements. k is 400. If you sort the whole array, you sort 1 mil If you use heapSort but k times, you only sort 400. You only sort as much as you need, kind of.

[@amitamar9852]

Great video! But there is a better solution that is running in linear time with O(1) memory, which is better than O(nlogk) with O(k) space. This algorithm is called the “Selection Algorithm”, which was invented in 1973.

[@mohitsonwane804]

Hey! I have a better solution to implement. Instead of heap push and heappushpop(), we can just use heapify method from beginning onwards and iterate through the array (n - k) times. heapq.heapify(nums) while len(nums) > k: heapq.heappop(nums) return nums[0]

[@LogicTherapy]

Why not just: return heapq.nlargest(k,nums)[-1] this is nlogk time too.