Find Median from Data Stream in Java: Explanation & Practice

Problem summary

Design a data structure that supports adding numbers and finding the median. Use two heaps approach.

Starter code

public class Main {
    public static void main(String[] args) {
        // addNum(1), addNum(2), findMedian() → 1.5
        // addNum(3), findMedian() → 2
        // Use max-heap for lower half, min-heap for upper half
        // Print medians after each findMedian()
    }
}

Expected output and test cases

• Add 1,2,3 → medians 1.5, 2

  1.5
  2.0

• Add 2,3,4

  2.0
  2.5
  3.0

• Single element

  5.0

Hints

1. Max-heap stores smaller half, min-heap stores larger half
2. Keep heaps balanced (sizes differ by at most 1)
3. Median is either top of larger heap or average of both tops
4. When adding, add to appropriate heap, then rebalance

Related Data Structures & Algorithms exercises

• Practice Merge K Sorted Lists in Java
• Practice Top K Frequent Elements in Java
• Practice Meeting Rooms II in Java

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler