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.
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.
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.
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)
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)
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!
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
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?
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” :)
amazing work, if we have heap size of k though , isn't the add() function can run in O(log k) time complexity ? since were pushing elements to heap in the size of k? or is it because k can be really big, lets say n-1, we kept almost the original heap size, than O(log n) is the worst case?
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,.
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.
🎯 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
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
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.
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?
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?
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
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.
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.
exactly, the question was so vague, I was scratching my head with what they wanted me to do.
Definitely medium.
Vhi na bhai
Love your content keep up the great work!
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.
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)
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
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
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.
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
The problem is not explained properly in the question at the source. This was supposed to be easy.
Can't we skep add if len >= k and val
Thanks for the great videos. Can you do a video on how you shoot the videos and what software/tools you use?
Easy and beginner level heap questions were needed, thank you for adding. Very good explanations.
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!
I'm here because I don't understand description
Thanks a lot, great explanation
Poping from the minimu value from the heap is O( log(n) ) not O( 1 )
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
I'm brutal fascinated how this problem is good and how this appoarch of thinking will grow my mind.
I love you neet
Love your content. Thank you so much for your effort
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?
Hi Neetcode, please I'm stuck on the problem "Accounts Merge" LC 721 please could you do a video solution on it, thanks!
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
Such a good explanation, thank you.
amazing work, if we have heap size of k though , isn't the add() function can run in O(log k) time complexity ? since were pushing elements to heap in the size of k? or is it because k can be really big, lets say n-1, we kept almost the original heap size, than O(log n) is the worst case?
The constructor definitely helps us reduce the time complexity to O(logk)
to master this code....what topics should i have to learn?
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,.
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.
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.
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?
Not all languages do have Heap in their std library. I expected to see the implemented heap on array
what if you were not allowed to use the built in heap structure? that would make this problem hard
great explanation
Superb as always!
What is the space complexity?
can't we have count logic and we can do in O(n)?
why not use a max heap?
🎯 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
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
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
Using the built in python hep functions if cheating. knowing how to maintain the heap is the whole point of these questions
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.
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]
Great video
The problem is disliked because the way it is written is far from "Clear Explanation". Sometimes authors of Leetcode problems take very heavy drugs
Thanks man, liked
what if we were asked to not use built in library
they won't
@@rahulbera454 thank you
Well they have changed this question from easy to medium.
False
this guy is so fucking smart.
Who is here at August 12. 2024?
Thank you for such an easy solution.
Hi,
Can we use Priority Queue?
Or we should use the approach which you have mentioned, it may impress interviewer.
No love for JS which doesn't have a built-in heapify function, huh
heapq object comes in clutch
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?
Explanation was medium and code part was easy
Thanks.
good luck in google
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?
This question is NOT easy LOL!
anyone here for problem of the day???
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 🔥🤩
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?