Kth Largest Element in a Stream - Leetcode 703 - Python

0:00 - Read the problem
2:20 - Drawing Explanation
8:10 - Coding Explanation

leetcode 703

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

[juanpablomesalopez]

Hey thanks for the videos.

Just wanted to add something.

Instead of adding each new val to the heap and poping the smallest value each time, you could first check if val >= minHeap[0]. Which is a O(1) operation. If it is True, then push val to heap and pop minimum value. Otherwise just skip the push and pop operations.

[fereshtehlux]

Thank you for the explanation. However, I want to mention that the time complexity is O(nlogk) not O(nlogn) since the size of heap is k then the depth and the number of operations to add a new value will be logk (not logn).

[lennythach]

Honestly, I didn't even understand what the question was even asking. spent 15min trying to understand it. lol, Thanks for the Explanation.
Now that I understand I'll try to solve it before looking at any solution.

[razisyed]

At 2:35, I think it's incorrect that it would take O(n) to find the kth largest element by scanning through the unsorted input.

It would take O(n)^2 as you would have to compare each element to every other element and count how many elements are larger than the current element. You would get your answer once you find an element for which there are k-1 larger elements. This could take O(n)^2 in the worst case.

And at 2:39, when the array is sorted, we don't need to use binary search. We can simply access the kth largest element at index n-k in O(1) time.

[accountutilitario]

🎯 Key Takeaways for quick navigation:

00:00 🎯 Introduction to Problem
- Introduction to the problem of finding the kth largest element in a stream of numbers.
- Explanation of the problem requirements, including the definition of "kth largest element in sorted order."
02:13 🤔 Problem Solving Approach
- Discussion of the naive approach: sorting the input array, binary search, and its limitations.
- Introduction of the optimal approach: using a min heap of size k to efficiently find the kth largest element in the stream.
- Explanation of the advantages of using a min heap and the reasoning behind its implementation for this problem.
08:20 💻 Implementation in Python
- Detailed walkthrough of the Python implementation of the problem solution.
- Explanation of the constructor function, initializing the min heap, and ensuring its size is k.
- Description of the add function, including how new elements are added to the min heap and maintaining its size.
- Demonstrated the efficient time complexity of the implemented solution and the significance of using a min heap for this problem.

Made with HARPA AI

[slomate]

wasn't able to understand the question and had to see your video for it. But after it I was able to come up with the solution pretty quickly.

[loccc]

Hey NeetCode, I just began to watch your videos only very recently. And I can safely say it's the most helpful resource out there including all the paid ones. As for this question, can you explain why you decided to pop from minHeap in both the _init_ and the add() functions? I just popped in the add() and it worked just fine.

[dmaynard]

Love your content keep up the great work!

[ku-]

I was confused with the time complexity of heappop. Getting the min value in a heap is O(1), but pop is O(log n) (not O(1)!) because log n elements has to be reordered after the pop. Don't get confused with arrays!

[kapilIT]

Can't we skep add if len >= k and val <= heap[0] ?

[clintondannolfo]

Good solution but could be amortized constant time `add` operation if we checked the min value on the heap before pushing it

[harunguven]

Easy and beginner level heap questions were needed, thank you for adding. Very good explanations.

[jenso]

so in javascript there is no function to convert an array into a heap.. you have to do it by hand.. and this is supposed to be an easy problem LOL

[kklr]

Thanks for the great videos. Can you do a video on how you shoot the videos and what software/tools you use?

[minciNashu]

heapq has two operations which do push and pop in one go, seemingly more efficient than separate calls
heapq.heapreplace and heapq.heappushpop

def add(self, val: int) -> int:
# case 1: empty heap
if len(self.nums) < self.k:
heapq.heappush(self.nums, val)
# case 2: k-sized heap, insert if value is higher than min; the check is optional, heapq also runs that check in the implementation
elif val > self.nums[0]:
heapq.heappushpop(self.nums, val)

return self.nums[0]

[dusvn]

I'm brutal fascinated how this problem is good and how this appoarch of thinking will grow my mind.
I love you neet <3

[kirillzlobin]

4:26 Cannot understand

If we are using mi heap, it means that in the beggining of the array we will have smaller values, how can we choose the largest ones among them?

[oualidlaib]

Poping from the minimu value from the heap is O( log(n) ) not O( 1 )

[sabaamanollahi]

Thank you so much for these contents, they are really helping!
just that in 2:40 I think the complexity in the sorted one is O(1) since we just want to pick a special index!

[hamsalekhavenkatesh]

Love this idea, another idea is to ise TreeMap where we store the element and its count...and we maintain its size to K... we add it to the treeMap only if min element is < newly added element. Still same time complexity but u r cautious not to add everytime into the treemap