What is the optimal time complexity of solving Find Median From Data Stream?

The optimized solution achieves a time complexity of O(n) by using sorting, mathematical shortcuts, or hash table lookups.

What is the auxiliary space complexity for Find Median From Data Stream?

The space complexity is O(1) since we only use a minimal/constant amount of extra memory for tracking variables (or auxiliary space if dynamic structures are allocated).

What are the typical edge cases we must handle in Find Median From Data Stream?

Key edge cases include empty collections, negative or large bounds causing integer overflow, arrays with only one element, or inputs where target criteria are not met.

How can we optimize the brute force approach for Find Median From Data Stream?

Brute force methods often inspect all possible combinations. We optimize this by sorting the input list to enable binary search, or tracking processed items in a set to avoid redundant nested loop lookups.

Back to Practice Dashboard

Top 150 InterviewHard

Find Median From Data Stream

Learn how to solve the 'Find Median From Data Stream' problem. This detailed resource details brute force and optimized approaches.

Mode Selected

Problem Statement

Hard

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

Implement the MedianFinder class:

- MedianFinder() Initializes the MedianFinder object.

- addNum(num: int) Adds the integer num from the data stream to the data structure.

- findMedian() -> float Returns the median of all elements so far.

Input is a list of operations and arguments. Implement a function medianFinder(operations: list, arguments: list) -> list that returns a list of results (None for constructor/addNum, float for findMedian).

Constraints

•-10^5 <= num <= 10^5
•There will be at least one element in the data structure before calling findMedian
•At most 5 * 10^4 calls will be made to addNum and findMedian

Examples

Example 1

Input

operations = ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"], arguments = [[], [1], [2], [], [3], []]

Output

[None, None, None, 1.5, None, 2.0]

Explanation

Initialize. Add 1, 2. Median is 1.5. Add 3. Median is 2.0.

Need a Hint?

Analyze the input constraints. Try sorting first (O(n log n)) or using a hash map/set to track seen elements in O(n) time.

Edge Cases to Watch

Empty list or null input variables
Single item lists/arrays
Extremely large input bounds causing integer or stack overflow

Ready to Solve?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

Open in Editor