{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Find Median from Data Stream – Solution & Complexity

Interview solutions
/
Find Median from Data Stream

Solution Walkthrough

  1. Step 1: Recognize the Pattern

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

  2. Step 2: Build the Algorithm

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

  3. Step 3: Check Edge Cases

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

  4. Step 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)K Closest Points to Origin solution (medium)Kth Largest Element in an Array solution (medium)Merge K Sorted Lists solution (hard)Task Scheduler solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?