295. Find Median from Data Stream

Description

Find the median in the data stream.

Pitfall

Common mistake:

public void addNum(int num) {
  // add to max, then adjust
  large.add(num);
  if (large.size() > small.size()) {
    small.add(large.remove());
  }
}

consider the following situation:

add(2);
add(3);
add(4);

add(-2);
add(-3);
add(-4);

Correct Soluton

public void addNum(int num) {
  small.add(num);
  large.add(small.remove());
  while (large.size() > small.size()) {
    small.add(large.remove());
  }
}