LeetCode Solution 295 - Find Median from Data Stream

Problem Statement

The problem requires us to design a data structure that supports the following operations efficiently:

1. addNum(int num): Adds an integer num to the data structure.
2. findMedian(): Returns the median of all elements added so far.

Example:

Input:

addNum(1)
addNum(2)
findMedian() → 1.5
addNum(3)
findMedian() → 2.0

Constraints:

• -10^5 <= num <= 10^5
• At most 5 * 10^4 calls will be made to addNum and findMedian.

---

Optimal Approach: Two Heaps (Min-Heap & Max-Heap)

Explanation:

1. Use two heaps:
   • Max-Heap (left) stores the smaller half of numbers.
   • Min-Heap (right) stores the larger half of numbers.
2. Balancing Heaps:
   • If sizes differ by more than 1, rebalance by moving an element.
3. Finding Median:
   • If both heaps are equal in size, median is the average of both tops.
   • Otherwise, median is the top of the larger heap.

C++ Implementation (LeetCode-Compatible)

#include <queue>
using namespace std;

class MedianFinder {
private:
    priority_queue<int> left; // Max-Heap
    priority_queue<int, vector<int>, greater<int>> right; // Min-Heap

public:
    MedianFinder() {}
    
    void addNum(int num) {
        if (left.empty() || num <= left.top()) {
            left.push(num);
        } else {
            right.push(num);
        }
        
        // Balance heaps
        if (left.size() > right.size() + 1) {
            right.push(left.top());
            left.pop();
        } else if (right.size() > left.size()) {
            left.push(right.top());
            right.pop();
        }
    }
    
    double findMedian() {
        if (left.size() == right.size()) {
            return (left.top() + right.top()) / 2.0;
        }
        return left.top();
    }
};

Step-by-Step Explanation

• Maintain two heaps: Max-Heap (left) and Min-Heap (right).
• Add new number: Place it in the correct heap.
• Balance heaps: Ensure left is never smaller than right.
• Find median:
  • If sizes are equal → Average of both tops.
  • If left is larger → Top of left.

---

Dry Run Example:

Input:

addNum(1)
addNum(2)
findMedian() → 1.5
addNum(3)
findMedian() → 2.0

Execution Steps:

Step	Left Heap (Max)	Right Heap (Min)	Median
addNum(1)	[1]	[]	1.0
addNum(2)	[1]	[2]	1.5
addNum(3)	[2,1]	[3]	2.0

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not Optimal?
Sorting (Brute Force)	O(N log N)	O(N)	Inefficient for large streams
Balanced BST (e.g., Red-Black Tree)	O(log N)	O(N)	More complex implementation
Using a Single Heap	O(log N)	O(N)	Harder to extract median efficiently

Sorting Approach (Alternative)

#include <vector>
#include <algorithm>
using namespace std;

class MedianFinder {
private:
    vector<int> nums;
public:
    void addNum(int num) {
        nums.push_back(num);
        sort(nums.begin(), nums.end());
    }
    double findMedian() {
        int n = nums.size();
        if (n % 2 == 0) {
            return (nums[n/2 - 1] + nums[n/2]) / 2.0;
        }
        return nums[n/2];
    }
};

Why is Sorting Less Optimal?

• Sorting on each insertion: O(N log N) per operation.
• Not suitable for streaming data.

---

Best Solution & Why?

Approach	Time Complexity	Space Complexity	Best Choice?
Two Heaps (Min & Max Heap)	O(log N)	O(N)	✅ Best balance
Sorting	O(N log N)	O(N)	❌ Too slow for streaming
Balanced BST	O(log N)	O(N)	❌ Harder to implement

Why is Two Heaps Best?

• Efficient O(log N) per operation ✅
• Works well for streaming data ✅
• Balanced approach between speed & memory ✅

---

Conclusion

• Best Solution: Two Heaps (Min & Max Heap).
• Why? Efficient O(log N) time, scalable, and easy to maintain.
• Alternative Solutions: Sorting (too slow), Balanced BST (complex).

Practice More:

• Kth Largest Element in an Array
• Sliding Window Median
• Find K Closest Elements