Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms in Go

Problem: Find Median from Data Stream

Understand how to implement a MedianOfStream class in Go that uses two heaps to track the median from a continually updating data stream. Learn to insert numbers efficiently and retrieve the median in constant time by balancing max and min heaps. This lesson covers the algorithmic design, implementation steps, and time-space complexity involved.

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.

  • For an even-sized list (e.g., [2,4,6,8][2, 4, 6, 8] ...