Thanks again for the most clear explanation of this problem I have found! Really appreciate the effort you put into these videos man! One thing that took me a while to grok when watching the video was on line 36 --- to maintain the invariant we initially set (max_heap has one extra element) its a lot more intuitive to change line 36 to "elif balance > 1" (where max_heap has more than 1 element out of balance). Of course, checking for "balance > 0" works here as well (since balance can only be either 0 or +/- 2).
I don't agree with this. While either check works for the reasons you stated, changing that check doesn't make sense logically. if I understand it correctly the balance variable doesn't represent the difference in the length of the heaps. for example, max_heap has 2 and min_heap has 1. balance is not -1 (or 1) BECAUSE of that difference. think of it this way: balance is initialized to 0 regardless of the invariant (odd/even elements), it only changes based on the element we're removing and the element we're adding. instead, balance represents that in this iteration, what changes we have to make to adjust. positive means adding to max_heap, negative means adding to min_heap. for example, if we remove an element in the right (min_heap) +1, and add an element to the right (min_heap) -1, then we have a balance of 0, it means that we don't need to do anything. for example, if we remove an element in the right -1 (min_heap), and add an element to the right (min_heap) -1, then we have a balance of -2, it means that we need to remove from the left and add to the right. the value itself doesn't matter as long as they cancel out when needed, the balance is more like a boolean checking for two conditions if that makes any sense
1. The SC seems wrong. Since you're using dict (hash table) to track the left most element that goes out of the sliding window, the SC should be O(N) 2. The expression, len(min_heap)
Hey I think, popping from a heap is not O(1), peaking is O(1). Popping itself is two steps delete -which like peak is O(1) - and then a restructuring of the heap, but this restructuring is log(n). So overall popping is a log(n) operation. Overall however, this is still better than the naiive way, searching and delete and restructure. Searching in a heap would be O(n). After the search it would require O(1) to delete and O(n) to re-build / restructure the heap (with heapify) in the worst case. In the best case here for the restructuring, it would take log(n) if the element is either at the top ( here the underlying operation is swap and bubble down) or the last element of the heap (here just delete and bubble up). Taking obviously the worst case, search O(n), delete O(1) and restructure O(n), overall this would be an O(n) operation.
Some questions I do this some questions the examples are too much of a hassle and not worth the trouble unfortunately. Just makes the videos take much longer to make and most people just watch the solution bit so it's lot a worthwhile return on investment
Hey this is the most clear explanation I have watched in recent times. Thanks man. Keep going! Suggestion: I think it would be better to divide things into different functions like add, remove, balance. One question: do you use the mouse to write it on the screen? (but it's hard to do that right)
This is too hard of a problem! I would solve it the naive way and pray for the next round- class Solution: def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]: lst = [] l=0 r=k while r
after you remove the element from max heap and min heap looping over in line 41 and 45, there could be scenario where the invariant of min_heap and max_heap is not maintained, like max_heap having equal or one more element than min heap. You should account for that right?
Can someone explain to me how this code deals with the scenario whereby the total number of elements in the heaps (both max_heap and min_heap) does not exceed the size of the sliding window k? The reason I am asking is because this code removes elements from the heap only when the root of the heap is found in heap_dict with a frequency of more than 0. I was thinking what if there is a scenario whereby the element that needs to be removed is not found in the root (but somewhere down the heap), as a result, based on the code, no elements would be removed. Therefore, when we slide the window, we add a new element into the heaps, resulting in the size of both heaps exceeding the size of the sliding window k.
I have understood. There will be cases whereby the size of both heaps will be more than k, which is more than the size of the window, but that is okay because as long as the top of the heaps are correct, and that our heaps are balanced, we can find the correct medium. So, time complexity wise, it is not exactly log(k) but more like log(k + (some small random number)). The time complexity will still be dominated by log(k)
![[CSES][Sorting and Searching] Sliding Cost](/img/n.gif)
Thanks again for the most clear explanation of this problem I have found! Really appreciate the effort you put into these videos man!
One thing that took me a while to grok when watching the video was on line 36 --- to maintain the invariant we initially set (max_heap has one extra element) its a lot more intuitive to change line 36 to "elif balance > 1" (where max_heap has more than 1 element out of balance).
Of course, checking for "balance > 0" works here as well (since balance can only be either 0 or +/- 2).
I don't agree with this. While either check works for the reasons you stated, changing that check doesn't make sense logically.
if I understand it correctly the balance variable doesn't represent the difference in the length of the heaps. for example, max_heap has 2 and min_heap has 1. balance is not -1 (or 1) BECAUSE of that difference. think of it this way: balance is initialized to 0 regardless of the invariant (odd/even elements), it only changes based on the element we're removing and the element we're adding.
instead, balance represents that in this iteration, what changes we have to make to adjust. positive means adding to max_heap, negative means adding to min_heap.
for example, if we remove an element in the right (min_heap) +1, and add an element to the right (min_heap) -1, then we have a balance of 0, it means that we don't need to do anything.
for example, if we remove an element in the right -1 (min_heap), and add an element to the right (min_heap) -1, then we have a balance of -2, it means that we need to remove from the left and add to the right.
the value itself doesn't matter as long as they cancel out when needed, the balance is more like a boolean checking for two conditions if that makes any sense
1. The SC seems wrong. Since you're using dict (hash table) to track the left most element that goes out of the sliding window, the SC should be O(N)
2. The expression, len(min_heap)
Hey I think, popping from a heap is not O(1), peaking is O(1). Popping itself is two steps delete -which like peak is O(1) - and then a restructuring of the heap, but this restructuring is log(n). So overall popping is a log(n) operation.
Overall however, this is still better than the naiive way, searching and delete and restructure. Searching in a heap would be O(n). After the search it would require O(1) to delete and O(n) to re-build / restructure the heap (with heapify) in the worst case. In the best case here for the restructuring, it would take log(n) if the element is either at the top ( here the underlying operation is swap and bubble down) or the last element of the heap (here just delete and bubble up). Taking obviously the worst case, search O(n), delete O(1) and restructure O(n), overall this would be an O(n) operation.
Yes I misspoke here. made this problem while I had a cold. The final overall complexity is still correct
so, how it is better than the normal approach?? We can still do this in overall O(n^2) time complexity without even using heaps?
What a horrible question! Thanks for doing this!
Before you write your code, could you give a simulated walkthrough of an example and then code it ? that would help make us understand it better
Some questions I do this some questions the examples are too much of a hassle and not worth the trouble unfortunately. Just makes the videos take much longer to make and most people just watch the solution bit so it's lot a worthwhile return on investment
Hey this is the most clear explanation I have watched in recent times. Thanks man. Keep going!
Suggestion: I think it would be better to divide things into different functions like add, remove, balance.
One question: do you use the mouse to write it on the screen? (but it's hard to do that right)
This is too hard of a problem! I would solve it the naive way and pray for the next round-
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
lst = []
l=0
r=k
while r
Popping from the top of the heap is O(logN) operation and not O(1) -- 6:02 and 23:43
yea I misspoke. the final complexities are still the correct ones
after you remove the element from max heap and min heap looping over in line 41 and 45, there could be scenario where the invariant of min_heap and max_heap is not maintained, like max_heap having equal or one more element than min heap. You should account for that right?
maybe the provided test cases didn't catch that case
Can someone explain to me how this code deals with the scenario whereby the total number of elements in the heaps (both max_heap and min_heap) does not exceed the size of the sliding window k?
The reason I am asking is because this code removes elements from the heap only when the root of the heap is found in heap_dict with a frequency of more than 0. I was thinking what if there is a scenario whereby the element that needs to be removed is not found in the root (but somewhere down the heap), as a result, based on the code, no elements would be removed.
Therefore, when we slide the window, we add a new element into the heaps, resulting in the size of both heaps exceeding the size of the sliding window k.
I have understood. There will be cases whereby the size of both heaps will be more than k, which is more than the size of the window, but that is okay because as long as the top of the heaps are correct, and that our heaps are balanced, we can find the correct medium. So, time complexity wise, it is not exactly log(k) but more like log(k + (some small random number)). The time complexity will still be dominated by log(k)
😈 *promosm*