Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Find Median from Data Stream

Explore how to implement a MedianOfStream class that maintains two heaps—a max-heap for the smaller half and a min-heap for the larger half of numbers—to efficiently find the median in O(1) time. Understand the balanced insertion and rebalancing process to keep median calculation constant, while handling dynamic data streams.

We'll cover the following...

Statement

Design a data structure that stores a dynamically changing list of integers and can find the median in constant time, O(1)O(1), as the list grows. To do that, implement a class named MedianOfStream with the following functionality:

  • Constructor(): Initializes an instance of the class.

  • insertNum(int num): Adds a new integer num to the data structure.

  • findMedian(): Returns the median of all integers added so far.

Note: The median is the middle value in a sorted list of integers.

  • For an odd-sized list (e.g., [4,5,6][4, 5, 6]), the median is the middle element: 55 ...