Heap
Find Median from Data Stream
hard
Count: 10
DESCRIPTION (inspired by Leetcode.com)
A live analytics dashboard starts with nums. New readings arrive in order in adds. After each incoming value is inserted, return the current median of all readings seen so far. If the count is even, the median is the average of the two middle values.
Example 1:
Inputs:
nums = [5, 2, 8] adds = [3, 10, 4]
Output:
[4, 5, 4.5]
Building Intuition
Approach 1: Sort Every Time
Why That Hurts
What Do We Actually Need?
Building Toward Heaps
Approach 2: Split the Stream Into Two Heaps
Pseudocode
Walkthrough
Solution
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium