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.
@@abenezermelaku2882 7 months later lol, but you could check if minHeap and val >= minHeap[0] This would allow the proper check w/out out of bounds error
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).
For the constructor: Popping from a heap of size n is logn. Do that n-k times. If n is much greater than k, popping from the heap (originally of size n) until the heap has a size of k would be O(n*logn) Time. For the add method: O(M*logk) Time Now that the heap is size k, popping is logk.
if you are constantly resizing the heap (making sure it is of length k) in each iteration of the loop in the constructor it is indeed nlogk. However, in Neet's solution, size adjustment is done at the end, then nlogn.
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.
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.
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!
"For Priority Queue / Queue data structures, you may use 5.4.0 version of datastructures-js/priority-queue and 4.2.3 version of datastructures-js/queue."
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)
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
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.
it's because when you first instantiate the stream, the number of elements in the heap could be greater than k. so like [4,5,8,2,1] and k = 3. so before adding, we have to pop all the elements until it becomes size k -> [4,5,8]. now when we do the add operation (lets say we are adding 6, heap becomes [4,5,8,6] but we also have to return the kth largest in the add operation. but our heap is more than k elements, so we have to pop AGAIN in add to make it k elements, and then finally we can return the first element of the heap (smallest element of heap of size k)
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.
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!
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.
feel bad because of that interview mindset. Its like we dont want you to use Google to search for thing, use your own custom-code from scratch search Engine
You’re allowed to directly use a built in heap in your preferred language. No need to implement it for a problem. Unless of course the problem is “implement a heap” :)
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,.
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?
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?
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?
🎯 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
it's because we're essentially using the min heap to cut off anything lower than k. All values that are smaller than minheap[0] are dropped, it is the smallest element of the min heap but it will always be the kth largest element
Because we need to find the new min once we remove the old min. We replace it with the rightmost and bottom most node in the heap and then bubble down.
n elements in array min heap keeps the min element at the top if n = 100, heapify the original array. length of minheap is now 100 if you want the the 3rd largest element from the original array, then pop the heap 97 times. now new element arrives. add to heap. heap is now len 4. Pop once, now again you have the 3rd largest lement at the top of minheap
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?
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.
That's a good optimization 👍
raises index out of range error if our input is empty
@@abenezermelaku2882 7 months later lol, but you could check if minHeap and val >= minHeap[0]
This would allow the proper check w/out out of bounds error
if (len(self.minHeap) < self.k or val > self.minHeap[0]):
heapq.heappush(self.minHeap, val)
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).
For the constructor:
Popping from a heap of size n is logn.
Do that n-k times.
If n is much greater than k, popping from the heap (originally of size n) until the heap has a size of k would be O(n*logn) Time.
For the add method:
O(M*logk) Time
Now that the heap is size k, popping is logk.
@@leetcoderafeeq2641 What is M, though?
@@markolainovic M are the number of calls to the add method
if you are constantly resizing the heap (making sure it is of length k) in each iteration of the loop in the constructor it is indeed nlogk. However, in Neet's solution, size adjustment is done at the end, then nlogn.
@@pacomarmolejo3492 this exactly
Definitely medium.
Vhi na bhai
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.
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.
This is exactly why I came to comments. I knew those 2 time complexities given are wrong. Thanks for the validation
Great correction thanks
Yea, when he said binary search i was tilting my entire head.
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!
What's the correct Time Complexity of the Add vs the __init__() then?
Thank you!
good reminder, thanks
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.
Good solution but could be amortized constant time `add` operation if we checked the min value on the heap before pushing it
Good point. It should be able to improve the runtime if the stream values are not monotonically increasing.
Love your content keep up the great work!
I'm here because I don't understand description
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
"For Priority Queue / Queue data structures, you may use 5.4.0 version of datastructures-js/priority-queue and 4.2.3 version of datastructures-js/queue."
Imagine leetcoding in javascript
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]
Idk I did that, but the runtime was longer when I tried it your way. Super weird. You'd think a dedicated function would work at least as well
I'm brutal fascinated how this problem is good and how this appoarch of thinking will grow my mind.
I love you neet
The problem is not explained properly in the question at the source. This was supposed to be easy.
Easy and beginner level heap questions were needed, thank you for adding. Very good explanations.
Poping from the minimu value from the heap is O( log(n) ) not O( 1 )
Can't we skep add if len >= k and val
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
The constructor definitely helps us reduce the time complexity to O(logk)
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.
it's because when you first instantiate the stream, the number of elements in the heap could be greater than k. so like [4,5,8,2,1] and k = 3. so before adding, we have to pop all the elements until it becomes size k -> [4,5,8]. now when we do the add operation (lets say we are adding 6, heap becomes [4,5,8,6] but we also have to return the kth largest in the add operation. but our heap is more than k elements, so we have to pop AGAIN in add to make it k elements, and then finally we can return the first element of the heap (smallest element of heap of size k)
Thanks a lot, great explanation
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.
Thanks for the great videos. Can you do a video on how you shoot the videos and what software/tools you use?
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!
How will you know the index?
We want to pick a special element and not Index bruh!
Such a good explanation, thank you.
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.
Lol
Most interviewers don't care. I think you just had a bad interviewer. Would they also expect you to implement quick sort if you needed to sort a list?
feel bad because of that interview mindset. Its like we dont want you to use Google to search for thing, use your own custom-code from scratch search Engine
Love your content. Thank you so much for your effort
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?
For curiosity, could we use builtin funciton or we should implement a simpler version of min-heap in actual coding interview?
You’re allowed to directly use a built in heap in your preferred language. No need to implement it for a problem. Unless of course the problem is “implement a heap” :)
@@apekplusplus or you are coding in javascript
Hi Neetcode, please I'm stuck on the problem "Accounts Merge" LC 721 please could you do a video solution on it, thanks!
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,.
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?
great explanation
Not all languages do have Heap in their std library. I expected to see the implemented heap on array
Superb as always!
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?
Thank You !... , Your explanation made my day : )
can i use the nlargest function in heapq python to initialize the length k heap instead of using while to pop extra element?
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?
awesome, thank you! can you do number of islands II? i'm so stuck on that one
u shud do a BFS...starting with 1 and mark visited as BFS is done.
Great video
My O(logK) solution. Beats 100% in Python:
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k = k
self.min_heap = []
for num in nums:
if len(self.min_heap) < k:
heapq.heappush(self.min_heap, num)
elif num > self.min_heap[0]:
heapq.heapreplace(self.min_heap, num)
def add(self, val: int) -> int:
if len(self.min_heap) < self.k:
heapq.heappush(self.min_heap, val)
elif val > self.min_heap[0]:
heapq.heapreplace(self.min_heap, val)
return self.min_heap[0]
what if you were not allowed to use the built in heap structure? that would make this problem hard
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.
False
Thank you for such an easy solution.
What is the space complexity?
Explanation was medium and code part was easy
this guy is so fucking smart.
🎯 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
But how. In the min heap 2 should be in the very beggining if we use 4, 5, 8, 2 values
can't we have count logic and we can do in O(n)?
heapq object comes in clutch
Thanks man, liked
how does self.minHeap[0] return the k largest element? The root of the min-heap should return the smallest element
Put n elements in a min heap, with n>=k. Then pop elements from the heap until there are exactly k elements in the heap. What does the root point to?
it's because we're essentially using the min heap to cut off anything lower than k. All values that are smaller than minheap[0] are dropped, it is the smallest element of the min heap but it will always be the kth largest element
Thanks.
No love for JS which doesn't have a built-in heapify function, huh
How is pop not a O(1) operation?
Because we need to find the new min once we remove the old min. We replace it with the rightmost and bottom most node in the heap and then bubble down.
what if we were asked to not use built in library
they won't
@@rahulbera454 thank you
The problem is disliked because the way it is written is far from "Clear Explanation". Sometimes authors of Leetcode problems take very heavy drugs
good luck in google
This question is NOT easy LOL!
heapq feels like cheating
This is pretty confusing.
n elements in array
min heap keeps the min element at the top
if n = 100, heapify the original array. length of minheap is now 100
if you want the the 3rd largest element from the original array, then pop the heap 97 times.
now new element arrives. add to heap. heap is now len 4. Pop once, now again you have the 3rd largest lement at the top of minheap
@@ninjaturtle205 🔥🤩
Who is here at August 12. 2024?
anyone here for problem of the day???
a cute prb
C++ solution please
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?