SLIDING WINDOW MEDIAN| LEETCODE 480 | PYTHON TWO-HEAP SOLUTION
Vložit
- čas přidán 9. 07. 2024
- Channel Discord Community: / discord
Problem Link: leetcode.com/problems/sliding...
Today we are solving a very tricky problem that involves finding the median of a sliding window. We'll need to use two heaps in order to keep everything in check but it definitely isn't trivial how we want to do this. We'll need to use our brains here to come up with a solution and hence the 30 minute long video.
TIMESTAMPS
00:00 Intro
00:07 Question Prompt
00:50 Basic Example
02:49 Solution Intuition
08:00 Coding
27:28Time/Space Complexity
29:15 Outro - Věda a technologie
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
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)
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).
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
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
😈 *promosm*