Buddy you don't know how much I appreciate you saying that this problem is hard again and again. This is because a lot of times when I'm not able to solve a problem it's extremely demotivating. However, knowing that others are struggling to solve this problem as well gives me some hope.
For people struggling with these types of problems, know that you should look up questions belonging to a particular pattern. Like this one can be put into line sweep algorithms or merge interval type questions. Once you get the intuition on how to deal with these types of problems, it becomes easy even with hard problems. For example I solved this question myself before coming to neetcode and checking out the video. I was able to solve it because I've solved similar questions, so # 2252 - Number of flowers in full bloom and # 1353 - Maximum Number of Events that can be attended. These problems are very similar with a little change in implementation. Also these types of problems can be solved using multiple methods. Heap/PQ, Using prefix sum with line sweep algo, or using 2 arrays with heap or two pointers. It is worth it to look up different solutions and invest time in understanding how each one works. Next time when you see a similar question, you will have all the tools needed to solve it
You mean that he doesn't pretend that the problem is easy and brag to everyone that the problem is easy and he was able to solve it. I can't solve this, this is ridiculous. When I saw the solution I thought what is this s...
A lot of these query problems can be cheesed using segment trees and there are a lot of other leetcode Problems like this. I actually found a brute force solution that got accepted by compressing the coordinates and jumping over seen spaces 😂 no heap needed
The way I handled the result indices was at the start, turning queries into a list of tuples like (query value i, i). That way we can still sort by value, but also access the correct index directly in our main loop and therefore keep result as a list. Its the same time and space the hashmap, but I think it might be a little cleaner.
This solution is brilliant because it LAZILY pops unwanted entries from the minHeap. For example, at 16:13, if there were a (100, 4) entry in the minHeap, you wouldn't care about it, because it wouldn't matter, as it wouldn't affect the result for query "5", which would be (4, 6).
Yes! I think this might have been worth going over in detail in the video, since it was hard to wrap my head around. Since we only care about the smallest length anyway, we can leave previous intervals in our minheap that are not the smallest. Otherwise, we can't use heappop at all - we would have to search for every interval to remove manually. This is what I was really stuck on
What's implicit is that we don't need to check the left value before popping because such an interval would have never made it to the heap if left value was greater than query - because we're sorting the queries. For example, for query 5, if there was a (1,7) in the interval, it would be wrong because 5 isnt in range [6,7], but (1,7) could have never made it to the heap for elements less than 5
It's not often you stumble upon a problem that's as beautiful as it is tough. The only thing I'm sad about is that you need to pop from the min heap after all, because a pure O(n logn) solution would've been the epitome of elegance.
If at all I get into META it will be only because of you . I have interview lined up. I will make sure to come back and reply here if I make it through
@@NeetCode I really enjoyed this question actually lol. I came up with basically the same solution but had to watch the video to see if you were about to teach us how to use segment trees lmao.
Here's my explanation of NeetCode's time complexity: Time = O(NlogN + QlogQ + Q + NlogN + NlogN) = O(NlogN + QlogQ) because we must sort both intervals and queries (i.e. O(NlogN + QlogQ) ), iterate thru the sorted queries (i.e. O(Q)), pop
and another thing is there are two ways to create a minHeap in Python: heapq.heappush() and heapq.heapify(). The difference btw them is heappush gonna maintain the existed data in an array, like [4,7,5] then heappush(0), it will be [ 0,4,7,5]. last but not least, it will be [0,4,5,7] if we heapify().
Thanks, another great tutorial! Question about the time complexity, wouldn't adding a new entry to the heap be an O(n) operation and so if we start with a heap of size 1 and end of up with a final size of n we will have an O(n^2) total time complexity in the worst case if we have to keep all the intervals in the heap? If so, wouldn't a sorted map structure e.g. with a balanced tree instead of a heap have a better time complexity e.g. similar to the idea used in solving skyline problem?
Maybe I missed it but what if two intervals start at the same point but have diff lengths? How would you be sure the shorter one is at the top of the heap?
Buddy you don't know how much I appreciate you saying that this problem is hard again and again. This is because a lot of times when I'm not able to solve a problem it's extremely demotivating. However, knowing that others are struggling to solve this problem as well gives me some hope.
++1
+=1
For people struggling with these types of problems, know that you should look up questions belonging to a particular pattern. Like this one can be put into line sweep algorithms or merge interval type questions. Once you get the intuition on how to deal with these types of problems, it becomes easy even with hard problems. For example I solved this question myself before coming to neetcode and checking out the video. I was able to solve it because I've solved similar questions, so # 2252 - Number of flowers in full bloom and # 1353 - Maximum Number of Events that can be attended. These problems are very similar with a little change in implementation. Also these types of problems can be solved using multiple methods. Heap/PQ, Using prefix sum with line sweep algo, or using 2 arrays with heap or two pointers. It is worth it to look up different solutions and invest time in understanding how each one works. Next time when you see a similar question, you will have all the tools needed to solve it
You mean that he doesn't pretend that the problem is easy and brag to everyone that the problem is easy and he was able to solve it. I can't solve this, this is ridiculous. When I saw the solution I thought what is this s...
A lot of these query problems can be cheesed using segment trees and there are a lot of other leetcode Problems like this. I actually found a brute force solution that got accepted by compressing the coordinates and jumping over seen spaces 😂 no heap needed
i love you bro, you're a legend. Going through your 150 list.
Were you able to get into FAANG?
Thanks a lot. I've been stuck with tutorials and couldn't find a good enough explanation. But you explained this question perfectly. 😇
Thanks, happy to help 🐻
The way I handled the result indices was at the start, turning queries into a list of tuples like (query value i, i). That way we can still sort by value, but also access the correct index directly in our main loop and therefore keep result as a list. Its the same time and space the hashmap, but I think it might be a little cleaner.
Great explanation bro 🔥🔥 you made a hard problem seem very easy, was stuck on it for 1 hr. coded in 5 mins after understanding the intuition
This guy is a gem. Awesome
This solution is brilliant because it LAZILY pops unwanted entries from the minHeap. For example, at 16:13, if there were a (100, 4) entry in the minHeap, you wouldn't care about it, because it wouldn't matter, as it wouldn't affect the result for query "5", which would be (4, 6).
Yes! I think this might have been worth going over in detail in the video, since it was hard to wrap my head around. Since we only care about the smallest length anyway, we can leave previous intervals in our minheap that are not the smallest. Otherwise, we can't use heappop at all - we would have to search for every interval to remove manually. This is what I was really stuck on
Thanks a lot Neetcode!! These videos make life so much easy.
What's implicit is that we don't need to check the left value before popping because such an interval would have never made it to the heap if left value was greater than query - because we're sorting the queries. For example, for query 5, if there was a (1,7) in the interval, it would be wrong because 5 isnt in range [6,7], but (1,7) could have never made it to the heap for elements less than 5
bro i love your explanations, thanks a lot from Russia!
It's not often you stumble upon a problem that's as beautiful as it is tough. The only thing I'm sad about is that you need to pop from the min heap after all, because a pure O(n logn) solution would've been the epitome of elegance.
Thanks, Neet! Interesting problem. Well explained!
Thanks Buddy, was able to submit my solution after getting the Explanation
If at all I get into META it will be only because of you . I have interview lined up. I will make sure to come back and reply here if I make it through
Did you make it
Thank you for your great explanation...!
i solved this question myselff : ))))))) i m soo happyyyyyyyyy
amazing video. this solution beat 100% in Python3
this is an atrocious question!!
Completely agree
@@NeetCode I really enjoyed this question actually lol. I came up with basically the same solution but had to watch the video to see if you were about to teach us how to use segment trees lmao.
Thank You, It helped a lot!
why time complexity of heappop() is not added into the overall complexity?
This is an insane problem 😮💨
great video, for time complexity, the loop over Q sorted queries has a heap push and pop operations (logN), wouldn't time complexity be Q*logQ*logN ?
Here's my explanation of NeetCode's time complexity:
Time = O(NlogN + QlogQ + Q + NlogN + NlogN) = O(NlogN + QlogQ) because we must sort both intervals and queries (i.e. O(NlogN + QlogQ) ), iterate thru the sorted queries (i.e. O(Q)), pop
thank you so much man
Great video!
Great video! Why didn't you have to use heapify?
We're not using heapify bc we're starting with an empty array (no values). heapify is only useful if we want to initialize a heap with several values.
and another thing is there are two ways to create a minHeap in Python: heapq.heappush() and heapq.heapify(). The difference btw them is heappush gonna maintain the existed data in an array, like [4,7,5] then heappush(0), it will be [ 0,4,7,5]. last but not least, it will be [0,4,5,7] if we heapify().
1851 the very recent problem of leetcode. Thanks. Dont know which time u r posting videos. In India, its 10 pm.
do a video on sudoku using backtracking
thanks a lot
Thanks, another great tutorial! Question about the time complexity, wouldn't adding a new entry to the heap be an O(n) operation and so if we start with a heap of size 1 and end of up with a final size of n we will have an O(n^2) total time complexity in the worst case if we have to keep all the intervals in the heap? If so, wouldn't a sorted map structure e.g. with a balanced tree instead of a heap have a better time complexity e.g. similar to the idea used in solving skyline problem?
adding a single element to an existing heap is O(logn)
does tiebreaker matter for this solution to work?
not really, the second value in minHeap is mainly to remove invalid intervals
Maybe I missed it but what if two intervals start at the same point but have diff lengths? How would you be sure the shorter one is at the top of the heap?
The min heap is sorted by interval length so the shortest will always appear at the front of the heap.
With this code, the heap keeps stale things that have a large value, popping first should reduce the memory used
6:02 it's value is 2 so what are we gonna do 😂😂
messy