Do you think you can? (3 Part Series)
There is a continuous stream of numbers that you are supplied with, wherein you get to know the new number added to that stream one at a time. At any given moment, you will be asked the question: what is the median in the current stream of numbers that you have seen so far? and you have to solve the problem with the most efficient solution.
- What data structure would you use to store the stream?
- What would be the time complexity of adding a number to the stream data structure that you are using?
- What would be the time complexity of fetching the real-time median at any given moment?
After giving it a try yourself, watch this video where I cover one of the most optimum solutions for the same problem:
Hope that helped, cheers!✌🏾