Problem
Submissions
Debug

Problem: Find Median from Data Stream

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]), the median is the average of the two middle elements: (4+6)/2=5(4 + 6) / 2 = 5.

Constraints:

  • −105≤-10^5 \leq num ≤105\leq 10^5, where num is an integer received from the data stream.

  • There will be at least one element in the data structure before the median is computed.

  • At most, 500500 calls will be made to the function that calculates the median.

Problem
Submissions
Debug

Problem: Find Median from Data Stream

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]), the median is the average of the two middle elements: (4+6)/2=5(4 + 6) / 2 = 5.

Constraints:

  • −105≤-10^5 \leq num ≤105\leq 10^5, where num is an integer received from the data stream.

  • There will be at least one element in the data structure before the median is computed.

  • At most, 500500 calls will be made to the function that calculates the median.