Introduction

Median Finder is a data structure that:

  • continuously receives numbers
  • efficiently returns the median
  • supports real-time updates

Goal:

  • insert numbers quickly
  • find median efficiently

Example:

addNum(1)Median = 1

addNum(2)
Median = 1.5

addNum(3)
Median = 2

Explanation:

Sorted Numbers:
[1]
[1,2]
[1,2,3]

This problem is one of the most important applications of:

Two Heaps

Constraints

-10^5 <= Number <= 10^5At most 5 * 10^4 operations

Approach : Two Heaps

Explanation

The idea is:

  • Max Heap stores smaller half
  • Min Heap stores larger half

Rules:

Max Heap contains smaller valuesMin Heap contains larger valuesSize difference must not exceed 1

Steps:

  1. Insert number.
  2. Place into correct heap.
  3. Balance heaps.
  4. Calculate median.

Observation:

Middle values always remain at the top of heaps.

This approach:

  • supports streaming data
  • provides efficient median lookup

Dry Run

Insert 1Max Heap:
[1]

Median = 1
----------------
Insert 2
Max Heap:
[1]

Min Heap:
[2]

Median:
(1 + 2) / 2 = 1.5
----------------
Insert 3
Max Heap:
[1]

Min Heap:
[2,3]

Median = 2

Practice

Complexity Analysis

addNum()
Time Complexity: O(log n) 

findMedian()
Time Complexity: O(1)

Space Complexity:
O(n)

Why This Problem is Important

This problem builds the foundation for:

  • Two Heaps Pattern
  • Streaming Data
  • Priority Queues
  • Real-Time Analytics
  • Online Algorithms

Real-World Applications

Used in:

  • Stock Market Analysis
  • Live Analytics Systems
  • Sensor Data Processing
  • Streaming Platforms
  • Financial Applications

Common Beginner Mistakes

  • Using only one heap
  • Not balancing heaps
  • Wrong heap ordering
  • Incorrect median calculation
  • Ignoring even-sized arrays

Interview Tip

Interviewers often expect:

  • Two Heaps explanation
  • Balancing logic
  • Streaming data reasoning
  • Complexity analysis

Always explain:

  • why two heaps are needed
  • how balancing works
  • why median becomes O(1)

Related Questions

  • Task Scheduler
  • Connect Ropes
  • Top K Frequent Elements
  • Merge K Sorted Lists
  • Kth Largest Element

Final Takeaway

The Median Finder problem is one of the most important Advanced Heap interview questions.

It teaches:

  • Two Heaps Pattern
  • Real-Time Median Calculation
  • Heap Balancing
  • Streaming Data Processing

Understanding this problem builds a strong foundation for:

  • advanced heap problems
  • online algorithms
  • interview-level data structures.