3 ms·
No, I mean median. Here is an article describing a very similar problem since I can’t link to the leetcode version: https://www.geeksforgeeks.org/median-of-stre
by Xcelerate 2y ago
No, I mean median. Here is an article describing a very similar problem since I can’t link to the leetcode version: https://www.geeksforgeeks.org/median-of-stream-of-running-integers-using-stl/ https://www.geeksforgeeks.org/median-of-stream-of-running-in...
- Tarean 2y agoBut that stores all elements into memory?
- raincole 2y ago> Auxiliary Space : O(n). > The Space required to store the elements in Heap is O(n). I don't think this algorithm is suitable for trillions of items.
- osti 2y agoI'm wondering what heap approach can solve that problem, as I can't think of any. Hopefully OP got a link to the thesis. The n log n approach definitely works though.