Definitely medium.

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.

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.

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).

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.

Love your content keep up the great work!

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

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

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.

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

Love your content. Thank you so much for your effort

Thanks a lot, great explanation

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.

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

Can't we skep add if len >= k and val

can i use the nlargest function in heapq python to initialize the length k heap instead of using while to pop extra element?

Hi Neetcode, please I'm stuck on the problem "Accounts Merge" LC 721 please could you do a video solution on it, thanks!

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!

Thank You !... , Your explanation made my day : )

Superb as always!

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

Such a good explanation, thank you.

The constructor definitely helps us reduce the time complexity to O(logk)

awesome, thank you! can you do number of islands II? i'm so stuck on that one

Thanks man, liked

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?

When we pop from the heap, how do we know that it is definitely the smallest element in the Heap? I.e. since a Heap only has a weak ordering, how is this guaranteed?

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

For curiosity, could we use builtin funciton or we should implement a simpler version of min-heap in actual coding interview?

Hi, Can we use Priority Queue? Or we should use the approach which you have mentioned, it may impress interviewer.

to master this code....what topics should i have to learn?

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]

great explanation

Great video

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!

shouldn't self.minHeap be initialized to nums[:] and not nums? that is, a copy of nums? in general, it's not a good idea to mutate the input provided. am i correct?

can't we have count logic and we can do in O(n)?

It's also worth mentioning that to find k largest number in a sorted array, you need constant time. Just take the kth element from the back of the array.

But how. In the min heap 2 should be in the very beggining if we use 4, 5, 8, 2 values

what if you were not allowed to use the built in heap structure? that would make this problem hard

Not all languages do have Heap in their std library. I expected to see the implemented heap on array

Just wanted to say I noticed that the self.k versus k usage is somewhat inconsistent. In some places, you use it, and in some areas, you don't. I don't know if this is a mistake or intentionally done. Either way, love your videos. Cheers,.

Thanks.

Thank you for such an easy solution.

heapq object comes in clutch

What is the space complexity?

I don't think this solution would pass at the higher levels of MAANG since using built-in helpers such as heapify disqualify you (happened to me during an interview at facebook a few years ago). They would want you to implement what heapify does from scratch, even if it's less efficient to do so in the langauge because they're rather see how you would go about doing so when you don't have built-ins to help you in your day-to-day work. Just food for thought.

How is pop not a O(1) operation?

how does self.minHeap[0] return the k largest element? The root of the min-heap should return the smallest element

Using the built in python hep functions if cheating. knowing how to maintain the heap is the whole point of these questions

Well they have changed this question from easy to medium.

🎯 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

what if we were asked to not use built in library

The problem is not explained properly in the question at the source. This was supposed to be easy.

Explanation was medium and code part was easy

I'm here because I don't understand description

No love for JS which doesn't have a built-in heapify function, huh

This question is NOT easy LOL!

a cute prb

good luck in google

The problem is disliked because the way it is written is far from "Clear Explanation". Sometimes authors of Leetcode problems take very heavy drugs

heapq feels like cheating

anyone here for problem of the day???

This is pretty confusing.

C++ solution please

Who is here at August 12. 2024?

shouldn't the constructor limit the heap size to k? creating a copy of nums and heapifying it would cost O(n log n), correct? in the constructor - we could add one integer at a time to the heap, and whenever the size of heap is bigger than k, we pop. code: ``` def __init__(self, k: int, nums: List[int]): # min heap with k largest integers self.min_heap = [] self.k = k for num in nums: heapq.heappush(self.min_heap, num) if len(self.min_heap) > k: heapq.heappop(self.min_heap) ``` thoughts?