Solution: Keep a Sorted List

The most direct idea is to keep every value in a list that is always sorted. If the list is sorted, the median is easy to read: it is the middle element, or the average of the two middle elements when the count is even. We reach those by index, so reading the median is $O(1)$.

The cost is in add. Our List has no method to insert at an index, so add puts the new value at the end, then shifts every larger value one slot right and writes the new value into the gap. This is the shifting inner loop of insertion sort from the quadratic sorting chapter.

public class SortedListMedianFinder implements MedianFinder {

  private List<Integer> sorted;  // every value so far, in ascending order

  public SortedListMedianFinder() {
    sorted = new ArrayList<>();
  }

  @Override
  public void add(int value) {
    sorted.add(value);  // at the end, then move it left into place
    int i = sorted.size() - 1;
    while (i > 0 && sorted.get(i - 1) > value) {
      sorted.set(i, sorted.get(i - 1));  // shift the larger value right
      i--;
    }
    sorted.set(i, value);
  }

  @Override
  public double median() {
    int count = sorted.size();
    if (count == 0) {
      throw new NoSuchElementException();
    }
    int mid = count / 2;
    if (count % 2 == 1) {
      return sorted.get(mid);  // odd count: the single middle value
    }
    return ((double) sorted.get(mid - 1) + sorted.get(mid)) / 2;
  }
}

Let’s trace add on the stream from the problem, 5, 2, 8, 1, 9, 3. The list stays sorted after every insert.

The first value just goes in.

┌───┐
│░5░│   size = 1
└───┘

Next we add 2. It belongs before 5, at index 0, so 5 shifts right to make room.

before:  ┌───┐
         │ 5 │
         └───┘
after:   ┌───┬───┐
         │░2░│ 5 │   size = 2
         └───┴───┘

We add 8. It is larger than everything, so it goes at the end and nothing shifts.

┌───┬───┬───┐
│ 2 │ 5 │░8░│   size = 3
└───┴───┴───┘

We add 1. It is smaller than everything, so it goes at index 0, and all three existing values shift right.

before:  ┌───┬───┬───┐
         │ 2 │ 5 │ 8 │
         └───┴───┴───┘
after:   ┌───┬───┬───┬───┐
         │░1░│ 2 │ 5 │ 8 │   size = 4
         └───┴───┴───┴───┘

We add 9. It is the largest, so it goes at the end and nothing shifts.

┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 5 │ 8 │░9░│   size = 5
└───┴───┴───┴───┴───┘

Finally we add 3. It belongs at index 2, between 2 and 5, so the three values 5, 8, 9 shift right.

before:  ┌───┬───┬───┬───┬───┐
         │ 1 │ 2 │ 5 │ 8 │ 9 │
         └───┴───┴───┴───┴───┘
after:   ┌───┬───┬───┬───┬───┬───┐
         │ 1 │ 2 │░3░│ 5 │ 8 │ 9 │   size = 6
         └───┴───┴───┴───┴───┴───┘

If we call median after each insert, we get 5, 3.5, 5, 3.5, 5, 4. That matches the problem statement.

Each add shifts every larger value one slot right, and a value inserted near the front shifts almost the whole list. With $n$ values already in the list, one insert is $O(n)$, the same as add in the sorted-array design from the priority queue chapter. Over $n$ inserts, the total is $O(n^2)$.

We pay this cost to keep every value in sorted order, but median only reads the one or two values in the middle.