20. Two-Heap Pattern: Find Median from Data Stream (Hard) • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

```
[ Small Numbers (Max-Heap) ]  ◀=== MEDIAN ===▶  [ Large Numbers (Min-Heap) ]
   (Stores smaller 50% data)                       (Stores larger 50% data)
```

---

### 2. LeetCode #295: Find Median from Data Stream

```python
import heapq

class MedianFinder:
    def __init__(self):
        # small is Max-Heap (stores negative values), large is Min-Heap:
        self.small = []
        self.large = []

def addNum(self, num: int) -> None:
        # 1. Push to small (Max-Heap):
        heapq.heappush(self.small, -num)

# 2. Balance property: small's max <= large's min
        if self.small and self.large and (-self.small[0] > self.large[0]):
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)

# 3. Size constraint: len(small) == len(large) or len(small) == len(large) + 1
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        elif len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)

def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return float(-self.small[0])
        return (-self.small[0] + self.large[0]) / 2.0
```
*Complexity:* `addNum` is $O(\log N)$, `findMedian` is ⚡ **$O(1)$ Constant Time!**

---

### 3. Master Comparison Matrix

| Data Structure | `addNum` Time | `findMedian` Time | Space Complexity |
| :--- | :--- | :--- | :--- |
| **Sorted Array (`bisect`)** | $O(N)$ (Shifting cost) | $O(1)$ | $O(N)$ |
| **Two Heaps (Max + Min)** | ⚡ **$O(\log N)$** | ⚡ **$O(1)$** | $O(N)$ |
| **Self-Balancing BST** | $O(\log N)$ | $O(\log N)$ | $O(N)$ |

---

### 4. Interview Ke 3 Sawal Is Topic Se

1. **Sliding Window Median (LeetCode #480) Two-Heap pattern se kaise solve hota hai?** -> Two Heaps + Lazy Deletion Hash Map maintain karke jo window se bahar gaye elements ko pop karte waqt clean karta hai.
2. **Find Median me agar saare numbers range $[0, 100]$ me hon toh kya optimal solution hoga?** -> Direct 101-size frequency bucket array banakar $O(1)$ time me median find kiya ja sakta hai.
3. **IPO Problem (LeetCode #502 Hard) me Two Heaps kaise use hoti hain?** -> Min-Heap by capital required + Max-Heap by profit to greedily pick highest profit available projects.

---
**Next Topic:** 21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal

Loading lesson content...

JavaScript

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track