Reference: LeetCode
Difficulty: Hard

Problem

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

For example,

  • [2,3,4], the median is 3

  • [2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

  • void addNum(int num) - Add a integer number from the data stream to the data structure.
  • double findMedian() - Return the median of all elements so far.

Example: 

1
2
3
4
5
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

Follow up: (Reference: Solutions to follow-ups)

  1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
  • We can maintain an integer array of length 100 to store the count of each number along with a total count. Then, we can iterate over the array to find the middle value to get our median. Time and space complexity would be O(100) = O(1).
  1. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?
  • In this case, we can keep a counter for lessThanHundred and greaterThanHundred. As we know the solution will be definitely in 0-100 we don’t need to know those number which are >100 or <0, only count of them will be enough.

Analysis

Reference: Solution Post

Simple Sorting

Every time we add in a new value, we need to re-sort the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private List<Integer> list = new ArrayList<>();

public void addNum(int num) {
  list.add(num);
  Collections.sort(list);
}

public double findMedian() {
  int n = list.size();
  if (n % 2 == 0) { // even
    return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
  } else { // odd
    return list.get(n / 2);
  }
}

Time: addNum() takes $O(N\log{N})$ 462 ms
Space: $O(N)$

Linear Search:

When a new number comes, we have to add it to the list while maintaining the sorted nature of the list. This is achieved easily by finding the correct place to insert the incoming number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private List<Integer> list = new ArrayList<>();

public void addNum(int num) {
  int n = list.size();
  int i = 0;
  while (i < n && list.get(i) < num) {
    ++i;
  } // i stops at a value >= num
  list.add(i, num);
}

public double findMedian() { // O(1)
  int n = list.size();
  if (n % 2 == 0) { // even
    return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
  } else { // odd
    return list.get(n / 2);
  }
}

Time: $O(N)$ 265 ms
Space: $O(N)$

Pop quiz Can we use binary search to improve efficiency? Sure!

Since the list is always sorted, we can use binary search.

Binary Search: (improvement)

Once the position is found, we need to shift all higher elements by one space to make room for the number, which takes $O(N)$.

Note: Here we use lower bound binary search since we need to find the position where the value is >= num.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private List<Integer> list = new ArrayList<>();

public void addNum(int num) {
  int n = list.size();
  int lo = 0, hi = n - 1;
  int mid;
  while (lo <= hi) { // takes O(logN)
    mid = lo + (hi - lo) / 2;
    int val = list.get(mid);
    if (val >= mid) {
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  list.add(lo, num); // takes O(N)
}

public double findMedian() { // O(1)
  int n = list.size();
  if (n % 2 == 0) { // even
    return (list.get(n / 2 - 1) + list.get(n / 2)) / 2.0;
  } else { // odd
    return list.get(n / 2);
  }
}

Time: $O(N)$ 76 ms

  • Binary search takes $O(\log{N})$ time.
  • Insertion can take up to $O(N)$ time.

Space: $O(N)$

Two Heaps

Idea: We only need a consistent way to access the median elements. Keeping the entire input sorted is not a requirement.

As it turns out there are two data structures for the job: heaps and self-balancing binary search trees.

Our goal is to maintain two heaps (balancing) in the following way:

  • A max-heap to store the smaller half of the input numbers.
  • A min-heap to store the larger half of the input numbers.
  • Constraint: The max-heap is allowed to store, at most, one more element than the min-heap does.

Steps: Add the new number to max-heap. Since the max-heap received a new element, we must do a balancing step for the min-heap.

  • Size Check (maxPQ > minPQ + 1): If the constraint is not satisfied, then remove the largest element from the max-heap and offer it to the min-heap.
  • Value Check (maxPQ.peek() > minPQ.peek()): Check the max value and min value from two heaps where maxVal <= minVal; otherwise, remove the largest element from the max-heap and offer it to the min-heap.
  • Size Check (maxPQ < minPQ): If the min-heap then holds one more elements than the max-heap after the previous operation. We fix that by removing the smallest element from the min-heap and offering it to the max-heap.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
private PriorityQueue<Integer> maxPQ;
private PriorityQueue<Integer> minPQ;

public MedianFinder() {
  maxPQ = new PriorityQueue<>((n1, n2) -> (n2 - n1));
  minPQ = new PriorityQueue<>((n1, n2) -> (n1 - n2));
}

public void addNum(int num) {
  // add num
  maxPQ.offer(num);
  // size check (max)
  if (maxPQ.size() - minPQ.size() > 1) {
    minPQ.offer(maxPQ.poll());
  }
  // value check
  if (maxPQ.size() > 0 && minPQ.size() > 0 && maxPQ.peek() > minPQ.peek()) {
    minPQ.offer(maxPQ.poll());
  }
  // size check (min)
  if (maxPQ.size() < minPQ.size()) {
    maxPQ.offer(minPQ.poll());
  }
}

public double findMedian() {
  if (maxPQ.size() == 0 && minPQ.size() == 0) {
    throw new IllegalArgumentException();
  }
  if (maxPQ.size() > minPQ.size()) { // odd
    return maxPQ.peek();
  } else { // even
    return (maxPQ.peek() + minPQ.peek()) / 2.0;
  }
}

Time: $O(5\log{N}) = O(\log{N})$
Space: $O(N)$

Multiset and Two Pointers

Reference: LeetCode Solution

It is based on self-balancing trees.