Find Median from Data Stream

Q: What is the time complexity of Find Median from Data Stream?

With two heaps, addNum is O(log n) , at most three heap pushes or pops, and findMedian is O(1) , two reads. Every value is stored, so space is O(n) . Sorting on every query costs O(n log n) per findMedian instead.

Q: Why not keep the values in a sorted array?

A sorted array answers findMedian in O(1) , and binary search finds where a new value goes in O(log n) . But inserting it shifts every value after that point, O(n) per addNum .

HardHeap

+10

Design a structure with two operations: addNum stores an integer, and findMedian returns the median of all values stored so far. The median of an odd count is the middle value; for an even count it is the average of the two middle values.

Operation i is ops[i], with values[i] holding the number for an addNum and 0 for a findMedian. Run them in order on an empty structure and return one string each: "null" for addNum, the median for findMedian. Write the median like "3", "2.5" or "-0.5": no decimal point for a whole number, and zero as "0", never "-0".

Function

medianStreamOps(ops: string-array, values: integer-array) → string-array

opsstring-array: the operations, in the order they run
valuesinteger-array: the number for each addNum, 0 for each findMedian
Returnsstring-array: one answer per operation, as text

Constraints

1 ≤ ops.length ≤ 3000
values.length == ops.length
Every ops[i] is addNum or findMedian.
-10⁵ ≤ values[i] ≤ 10⁵ for addNum, and values[i] == 0 for findMedian.
findMedian is only called after at least one addNum.

Examples

Input: ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]values = [5, 0, 1, 0, 8, 0, 3, 0]
Output: ["null", "5", "null", "3", "null", "5", "null", "4"]
Explanation: With 1 and 5 the median is (1 + 5) / 2 = 3. With 1, 5 and 8 it is 5, and with 1, 3, 5 and 8 it is (3 + 5) / 2 = 4.

Follow-up

If every value were between 0 and 100, how could you make both operations run in constant time?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The median sits between the two halves of the data, so the order inside each half does not matter: only the largest value of the lower half and the smallest of the upper half do. Two heaps keep exactly those two values on top. Each addNum costs O(log n) and each findMedian reads two tops in O(1).

Sort on every findMedian

Intuition

Store every value in a list. findMedian sorts it and reads the indexes (total-1)/2 and total/2, with integer division: the same index for an odd count, the middle pair for an even one. Add the two values and halve the sum, and you have the median either way.

Halve with integers. An even sum divides exactly. An odd sum becomes half its absolute value followed by .5, with the sum's sign, so -3 becomes -1.5.

Every query sorts again. With 1,500 adds and a query after each, that is around 10^7 comparisons, where the heaps need a few tens of thousands of steps.

Algorithm

Keep a list values.
For addNum x, append x and record "null".
For findMedian, sort values and add values[(total-1)/2] and values[total/2].
Halve the sum as text with integers and record it.

def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.values = []

    def addNum(self, x):
        self.values.append(x)

    def findMedian(self):
        self.values.sort()
        total = len(self.values)
        # For an odd count both indexes point at the one middle value.
        return half_text(self.values[(total - 1) // 2] + self.values[total // 2])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Two heaps split at the median

Intuition

Split the values into a lower half low and an upper half high, with every value of low at most every value of high, and low the same size as high or one larger. The median is low's largest value, or for an even count its average with high's smallest. A max-heap for low and a min-heap for high keep those values on top.

A new value goes into low if it is at most low's top, otherwise into high. When the sizes drift apart, move a top across: it is the value closest to the other half, so the order holds. An add is a few heap operations, O(log n), or O(n) in R, which copies the heap on every change.

After the first example's four adds, low holds 3 and 1 and high holds 5 and 8.

Algorithm

Keep a max-heap low for the lower half and a min-heap high for the upper half.
addNum x: push x into low if low is empty or x is at most its top, otherwise into high.
If low holds two more values than high, move low's top to high. If high holds more than low, move high's top to low.
findMedian: if low is larger, record its top. Otherwise add the two tops and halve the sum with integers.

import heapq


def half_text(total):
    # total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
    if total % 2 == 0:
        return str(total // 2)
    sign = "-" if total < 0 else ""
    return sign + str(abs(total) // 2) + ".5"


class MedianFinder:
    def __init__(self):
        self.low = []   # the smaller half; heapq is a min-heap, so it stores -x to keep the largest on top
        self.high = []  # the larger half, smallest on top

    def addNum(self, x):
        if not self.low or x <= -self.low[0]:
            heapq.heappush(self.low, -x)
        else:
            heapq.heappush(self.high, x)
        # Rebalance: low holds as many values as high, or one more.
        if len(self.low) > len(self.high) + 1:
            heapq.heappush(self.high, -heapq.heappop(self.low))
        elif len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def findMedian(self):
        if len(self.low) > len(self.high):
            return str(-self.low[0])
        return half_text(-self.low[0] + self.high[0])


def medianStreamOps(ops, values):
    finder = MedianFinder()
    result = []
    for op, x in zip(ops, values):
        if op == "addNum":
            finder.addNum(x)
            result.append("null")
        else:
            result.append(finder.findMedian())
    return result

Pitfalls and edge cases

Choosing the heap by size instead of by value. Pushing into the smaller heap without comparing breaks the order between the halves, and the tops stop being the middle values.
Halving with plain integer division. In C and Java -1 / 2 is 0, so appending .5 prints 0.5 for -0.5. In Python -3 // 2 is -2, which prints -2.5 for -1.5. Floating point prints 3.0 or 2.500000 in some languages.
Storing low negated in a min-heap and forgetting to negate back when you read its top or move a value to high.
Writing -0. Middle values -1 and 1 sum to 0, and the answer is "0".

Frequently asked questions3

What is the time complexity of Find Median from Data Stream?

With two heaps, addNum is O(log n), at most three heap pushes or pops, and findMedian is O(1), two reads. Every value is stored, so space is O(n). Sorting on every query costs O(n log n) per findMedian instead.

Why not keep the values in a sorted array?

A sorted array answers findMedian in O(1), and binary search finds where a new value goes in O(log n). But inserting it shifts every value after that point, O(n) per addNum.

Can you find the exact median of a stream without storing every value?

Not in general. Any value seen so far can become the median later, depending on what arrives next, so an exact answer needs all of them.

def medianStreamOps(ops, values):
    # Write code here

Test #1

Test #2

Arguments

ops = ["addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian", "addNum", "findMedian"]
values = [5, 0, 1, 0, 8, 0, 3, 0]

Expected Output

["null", "5", "null", "3", "null", "5", "null", "4"]