Practice/Meta/Leetcode 295. Find Median from Data Stream

Leetcode 295. Find Median from Data Stream

CodingMust

Problem

Design a data structure that efficiently tracks the median of a stream of integers. Your structure must support two operations:

• addNum(num): Insert an integer into the data stream
• findMedian(): Return the current median of all elements added so far

The median is the middle value in a sorted list. For an odd number of elements, it's the middle element. For an even number of elements, it's the average of the two middle elements.

Your implementation should handle frequent interleaved calls to both operations efficiently.

Requirements

1. Implement a MedianFinder class with an __init__ method
2. Implement addNum(num) to add an integer to the stream
3. Implement findMedian() to return the current median as a float
4. Handle both odd and even counts of numbers correctly
5. Optimize for scenarios with many interleaved operations

Constraints

• -105 ≤ num ≤ 105
• At most 5 × 104 calls will be made to addNum and findMedian
• findMedian will only be called when at least one number has been added
• Target time complexity: O(log n) for addNum, O(1) for findMedian

Examples

Example 1:

` Operations: ["MedianFinder", "addNum", "findMedian", "addNum", "findMedian"] Arguments: [[], [1], [], [2], []] Output: [null, null, 1.0, null, 1.5]

Explanation: MedianFinder mf = new MedianFinder(); mf.addNum(1); // stream = [1] mf.findMedian(); // returns 1.0 mf.addNum(2); // stream = [1, 2] mf.findMedian(); // returns (1 + 2) / 2 = 1.5 `

Example 2:

` Operations: ["MedianFinder", "addNum", "addNum", "addNum", "findMedian"] Arguments: [[], [3], [1], [2], []] Output: [null, null, null, null, 2.0]

Explanation: After adding 3, 1, and 2, the sorted stream is [1, 2, 3] The median is the middle element: 2.0 `

Example 3:

` Operations: ["MedianFinder", "addNum", "addNum", "addNum", "addNum", "findMedian"] Arguments: [[], [1], [3], [5], [7], []] Output: [null, null, null, null, null, 4.0]

Explanation: Stream is [1, 3, 5, 7], median is (3 + 5) / 2 = 4.0 `