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

Solution: Find Median from Data Stream

Explore how to implement a MedianOfStream class using two heaps—a max-heap and a min-heap—to maintain balance and efficiently find the median in a dynamically changing list of integers. Understand the comparison with naive sorting methods, and learn the optimal approach to achieve O(log n) insertion and O(1) median retrieval time complexities.

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 ...