You would probably see me in all your videos at this point but I appreciate you man! Thank you! I pray I get my faang job soon with the effor Tim putting in!
Can you tell me why not do this instead? def findKthLargest(self, nums: List[int], k: int) -> int: #max heap creation negatedNums = [-x for x in nums] heapq.heapify(negatedNums) returnElement = -1 #remove k elements while k>0: returnElement = heapq.heappop(negatedNums) k-=1 return -1*returnElement Runtime to create the heap is O(N) and runtime to pop an element is O(logN) and we do it K times = O(N + kLogN) = O(kLogN) is that not enough? How do justify O(NLogK) is better than this?
Wanted to bump this. I think the above comment has better time complexity but worse space complexity (O(N) > O(K)) as K is bounded by N, so shouldn't the better solution depend on whether we are optimizing toward time complexity or space complexity?
It really clear explanation, and also shows the time and space complexity.
You would probably see me in all your videos at this point but I appreciate you man! Thank you! I pray I get my faang job soon with the effor Tim putting in!
Great video what does it mean heapq and why you didn't import it to use it
heapq is the Python standard library for heaps. In Leetcode it's basically globally imported for you so you don't have to write `import heapq`
Can you tell me why not do this instead?
def findKthLargest(self, nums: List[int], k: int) -> int:
#max heap creation
negatedNums = [-x for x in nums]
heapq.heapify(negatedNums)
returnElement = -1
#remove k elements
while k>0:
returnElement = heapq.heappop(negatedNums)
k-=1
return -1*returnElement
Runtime to create the heap is O(N) and runtime to pop an element is O(logN) and we do it K times = O(N + kLogN) = O(kLogN) is that not enough? How do justify O(NLogK) is better than this?
I believe when you heapify nums, you need to perform a heap operation for N items, resulting in O(NlogN) every time?
Wanted to bump this. I think the above comment has better time complexity but worse space complexity (O(N) > O(K)) as K is bounded by N, so shouldn't the better solution depend on whether we are optimizing toward time complexity or space complexity?
Why you don't implement heap data structure instead of using heapq
Why would I do that, it's complete overkill.
Have a Meta interview coming up. Would interviewer expect heap implementation or is using heapq fine in most cases?
@@a.j1031 using a heapq is fine. good luck!