{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Find Median from Data Stream – Solution & Complexity

Interview solutions
/
Find Median from Data Stream

1. Recognize the Pattern

The key pattern is: Two heaps balance the lower and upper halves. Identify the state and invariant before coding.

2. Build the Algorithm

Advance one state transition at a time. Mark or update state before exploring dependent work.

3. Check Edge Cases

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

4. Solution and Complexity

Time: O(n log n). Space: O(n).

def find_median(nums: list[int]) -> float:
    import heapq
    low, high = [], []
    for number in nums:
        heapq.heappush(low, -number)
        heapq.heappush(high, -heapq.heappop(low))
        if len(high) > len(low):
            heapq.heappush(low, -heapq.heappop(high))
    return float(-low[0]) if len(low) > len(high) else (-low[0] + high[0]) / 2

FAQ

See also

Practice Find Median from Data Stream online (run code in the browser)Kth Largest Element in an Array solution (medium)Merge K Sorted Lists solution (hard)Top K Frequent Elements solution (medium)Design Add and Search Words solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?