Find Median from Data Stream: the idea to remember.

The core insight

Keep the lower half in a max heap and the upper half in a min heap. Lower has the same size or one extra element.

Why it works

All lower values are at most all upper values. Balanced sizes place the middle value or middle pair at the heap roots.

The mistake to avoid

Promote to long before averaging two int values to avoid overflow. Querying the median assumes at least one inserted value.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

class MedianFinder {
    private final PriorityQueue<Integer> lower = new PriorityQueue<>(Comparator.reverseOrder());
    private final PriorityQueue<Integer> upper = new PriorityQueue<>();
    void addNum(int n) {
        if (lower.isEmpty() || n <= lower.peek()) lower.add(n); else upper.add(n);
        if (lower.size() > upper.size() + 1) upper.add(lower.remove());
        if (upper.size() > lower.size()) lower.add(upper.remove());
    }
    double findMedian() {
        if (lower.size() > upper.size()) return lower.peek();
        return ((long) lower.peek() + upper.peek()) / 2.0;
    }
}

Make the next connection