Problem link ও উৎস
- **Original source:** Classic running-median via two balanced heaps
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Hard
- **Pattern:** Two heaps (lower half max-heap + upper half min-heap)
- **Basic idea inherited from:** `08` two-heaps pattern — max-heap-via-negation + invariant maintenance
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা data stream থেকে এক এক করে সংখ্যা আসছে। তোমাকে একটা structure বানাতে হবে যেটা দুটো কাজ করে: `addNum(x)` — stream-এ একটা নতুন সংখ্যা যোগ করা, আর `findMedian()` — এখন পর্যন্ত দেখা সব সংখ্যার **median** ফেরত দেওয়া। সংখ্যা জোড় হলে median = মাঝের দুটোর গড়; বিজোড় হলে ঠিক মাঝেরটা।
```text
addNum(1); addNum(2) -> findMedian() = 1.5
addNum(3) -> findMedian() = 2
```
### Input ও output {#8-example-input-and-output}
```text
addNum(1), addNum(2) -> findMedian() = 1.5
addNum(3) -> findMedian() = 2.0
addNum(5),addNum(2),addNum(8),addNum(1) -> findMedian() = 3.5
শুধু addNum(4) -> findMedian() = 4.0 (একটাই সংখ্যা)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা **দাঁড়িপাল্লা (seesaw), যার pivot-এ median**। বাঁ পাল্লায় ছোট সংখ্যাগুলো, ডান পাল্লায় বড়গুলো। প্রতিটা heap শুধু তার ভেতরের কিনারাটা — মাঝখান ছুঁয়ে থাকা value-টা — দেখায়। দুই পাল্লা প্রায় সমান ভারী রাখো (পার্থক্য বড়জোর 1), তাহলে মাঝখানের value(s) সবসময় হাতের নাগালে; সেটাই median।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত `08`-এর **two-heaps pattern** আর **max-heap-via-negation**। সংখ্যাগুলোকে দুই অর্ধে ভাগ করো — ছোট অর্ধ একটা max-heap-এ, বড় অর্ধ একটা min-heap-এ। median সবসময় এই দুই heap-এর top-এই লুকিয়ে। আর প্রতিটা insert-এর পরে একটা invariant (size balance) ধরে রাখা — sliding-window-ধাঁচের "প্রতি step-এ property maintain" চিন্তা।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: median মানে "ঠিক মাঝখানের" value(s)। যদি ছোট অর্ধটা একটা max-heap-এ (top = ছোটদের মধ্যে সবচেয়ে বড়) আর বড় অর্ধটা একটা min-heap-এ (top = বড়দের মধ্যে সবচেয়ে ছোট) রাখি, আর দুটোর size বড়জোর 1-এর ব্যবধানে রাখি, তাহলে median সবসময় এক বা দুই peek দূরে — কোনো sorting লাগে না।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
**দুটো heap।** (1) `lower` — ছোট অর্ধের **max-heap** (heapq min-heap বলে value negate করে রাখা)। (2) `upper` — বড় অর্ধের **min-heap**। Invariant: `len(lower) == len(upper)` বা `len(lower) == len(upper) + 1`।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
`findMedian`-এ দরকার শুধু **দুই অর্ধের ভেতরের কিনারা** — সম্পূর্ণ sorted order না। দুটো heap-এর top ঠিক সেই দুই middle value দেয়, peek O(1)। `addNum`-এ একটা push + বড়জোর একটা rebalance move, দুটোই O(log n)। প্রতিবার পুরো stream sort করার (O(n log n) প্রতি query) দরকারই পড়ে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সব সংখ্যা একটা list-এ জমাও। `findMedian` ডাকলে list-টা sort করো, তারপর মাঝের element (বা দুটোর গড়) নাও।
```text
addNum push করো list-এ ; findMedian -> list sort -> মাঝখান নাও
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিবার `findMedian`-এ পুরো list sort মানে query-প্রতি **O(n log n)**; q-টা query হলে মোট O(q·n log n)। insert-এ sorted রাখলেও insertion O(n) (shift)। অথচ median পেতে পুরো order লাগেই না — শুধু মাঝের দুটো value, যা দুটো heap O(1)-এ দেয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: median শুধু **মাঝের এক বা দুই value**-এর উপর নির্ভর করে, পুরো sorted list-এর উপর না। সংখ্যাগুলোকে দুই balanced অর্ধে রাখলে সেই middle value(s) = দুই heap-এর top। তাই insert O(log n), median query O(1)।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`addNum(x)`: প্রথমে `lower` (max-heap)-এ push করে তার top `upper`-এ সরাও (যাতে partition ঠিক থাকে), তারপর size balance করো — `upper` বড় হয়ে গেলে তার top `lower`-এ ফেরত আনো। Invariant: `lower`-এ হয় সমান, নয় একটা বেশি। `findMedian`: size সমান হলে `(lower_top + upper_top)/2`, নাহলে `lower_top`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "median বের করা" না ভেবে ভাবো "দুটো balanced heap যাদের top দুটো ঠিক মাঝখান ছুঁয়ে আছে — insert-এ শুধু partition আর balance ঠিক রাখি।" "median of a stream / window / balance two halves" — এমন কথা শুনলেই two-heaps (lower max + upper min)-এর কথা মাথায় আসা উচিত।
### ছবিতে বোঝা {#7-visual-explanation}
`5, 2, 8, 1` যোগ করার পর — `lower` max-heap (ছোট অর্ধ), `upper` min-heap (বড় অর্ধ):
```text
lower (max-heap) | upper (min-heap)
[2, 1] | [5, 8]
top = 2 ----------+---------- top = 5
median = (2 + 5) / 2 = 3.5
আরেকটা যোগ: addNum(3) ->
lower [3, 2, 1] | upper [5, 8] (size 3 vs 2)
top = 3 | top = 5
median = 3 (lower বড়, তার top)
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`addNum(1)`, `addNum(2)`, তারপর `findMedian()`; পরে `addNum(3)`, `findMedian()`:
1. addNum(1): lower-এ push 1 → lower top 1 → upper-এ সরাও → upper [1], lower []; upper বড় (1 vs 0) → top 1 lower-এ ফেরত → lower [1], upper []
2. addNum(2): lower-এ push 2 → lower top 2 → upper-এ সরাও → upper [2], lower [1]; size 1 vs 1, balanced
3. findMedian(): size সমান → (lower_top 1 + upper_top 2)/2 = 1.5
4. addNum(3): lower-এ push 3 → lower top 3 → upper-এ সরাও → upper [2,3], lower [1]; upper বড় (2 vs 1) → top 2 lower-এ ফেরত → lower [1,2], upper [3]
5. findMedian(): lower বড় (2 vs 1) → lower_top = 2
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
class MedianFinder:
def __init__(self):
self.lower = [] # ছোট অর্ধ: max-heap (negate করে রাখা)
self.upper = [] # বড় অর্ধ: min-heap
def addNum(self, num):
# ১) আগে lower-এ ঢালো, তার top upper-এ সরাও (partition ঠিক রাখো)
heapq.heappush(self.lower, -num)
heapq.heappush(self.upper, -heapq.heappop(self.lower))
# ২) size balance: lower-এ সমান বা একটা বেশি থাকবে
if len(self.upper) > len(self.lower):
heapq.heappush(self.lower, -heapq.heappop(self.upper))
def findMedian(self):
if len(self.lower) > len(self.upper):
return float(-self.lower[0]) # বিজোড়: lower-এর top
return (-self.lower[0] + self.upper[0]) / 2.0 # জোড়: দুই top-এর গড়
# ---- tests ----
mf = MedianFinder()
mf.addNum(1)
mf.addNum(2)
assert mf.findMedian() == 1.5
mf.addNum(3)
assert mf.findMedian() == 2.0
mf2 = MedianFinder()
for x in [5, 2, 8, 1]:
mf2.addNum(x)
assert mf2.findMedian() == 3.5 # sorted [1,2,5,8] -> (2+5)/2
mf3 = MedianFinder()
mf3.addNum(4)
assert mf3.findMedian() == 4.0 # একটাই সংখ্যা
mf4 = MedianFinder()
for x in [-1, -2, -3]:
mf4.addNum(x)
assert mf4.findMedian() == -2.0 # sorted [-3,-2,-1] -> মাঝখান -2
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `self.lower = []` / `self.upper = []` — ছোট অর্ধের max-heap (negate করা) আর বড় অর্ধের min-heap।
- `heapq.heappush(self.lower, -num)` — নতুন সংখ্যা আগে ছোট অর্ধে (negate করে max-heap-এ)।
- `heapq.heappush(self.upper, -heapq.heappop(self.lower))` — lower-এর সবচেয়ে বড়টা upper-এ পাঠাও, যাতে partition (ছোট vs বড়) ঠিক থাকে।
- `if len(self.upper) > len(self.lower): ...` — upper বড় হয়ে গেলে তার top lower-এ ফেরত; invariant — lower ≥ upper, পার্থক্য বড়জোর 1।
- `if len(self.lower) > len(self.upper): return float(-self.lower[0])` — মোট সংখ্যা বিজোড় হলে median = lower-এর top।
- `return (-self.lower[0] + self.upper[0]) / 2.0` — জোড় হলে দুই top-এর গড়।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`addNum(1), addNum(2)` পরে `findMedian()` section 14-এর dry run মেনে 1.5 দেয়; `addNum(3)`-এর পরে 2.0। `[5,2,8,1]`-এ sorted [1,2,5,8] → (2+5)/2 = 3.5; single 4 → 4.0; negative `[-1,-2,-3]` → মাঝখান −2.0। median একটা নির্দিষ্ট value, তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// Node-এ built-in heap নেই; একটা minimal binary heap, cmp দিয়ে min/max ঠিক করি
class Heap {
constructor(cmp) { this.a = []; this.cmp = cmp; } // cmp(a,b)<0 হলে a আগে
get size() { return this.a.length; }
peek() { return this.a[0]; }
push(x) {
const a = this.a, c = this.cmp; a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (c(a[p], a[i]) <= 0) break;
[a[p], a[i]] = [a[i], a[p]]; i = p;
}
}
pop() {
const a = this.a, c = this.cmp, top = a[0], last = a.pop();
if (a.length) {
a[0] = last; let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2; let best = i;
if (l < a.length && c(a[l], a[best]) < 0) best = l;
if (r < a.length && c(a[r], a[best]) < 0) best = r;
if (best === i) break;
[a[best], a[i]] = [a[i], a[best]]; i = best;
}
}
return top;
}
}
class MedianFinder {
constructor() {
this.lower = new Heap((a, b) => b - a); // ছোট অর্ধ: max-heap (cmp উল্টানো)
this.upper = new Heap((a, b) => a - b); // বড় অর্ধ: min-heap
}
addNum(num) {
// ১) আগে lower-এ ঢালো, তার top upper-এ সরাও (partition ঠিক রাখো)
this.lower.push(num);
this.upper.push(this.lower.pop());
// ২) size balance: lower-এ সমান বা একটা বেশি থাকবে
if (this.upper.size > this.lower.size) this.lower.push(this.upper.pop());
}
findMedian() {
if (this.lower.size > this.upper.size) return this.lower.peek(); // বিজোড়
return (this.lower.peek() + this.upper.peek()) / 2; // জোড়: গড়
}
}
// ---- test cases ----
const mf = new MedianFinder();
mf.addNum(1); mf.addNum(2);
assert(mf.findMedian() === 1.5, "1.5");
mf.addNum(3);
assert(mf.findMedian() === 2, "2");
const mf2 = new MedianFinder();
for (const x of [5, 2, 8, 1]) mf2.addNum(x);
assert(mf2.findMedian() === 3.5, "3.5");
const mf3 = new MedianFinder();
mf3.addNum(4);
assert(mf3.findMedian() === 4, "একটাই");
const mf4 = new MedianFinder();
for (const x of [-1, -2, -3]) mf4.addNum(x);
assert(mf4.findMedian() === -2, "negative -2");
console.log("সব JS test pass!");
```
> **JS টীকা:** **JS-এ built-in heap নেই**, তাই একটা generic `Heap` লিখলাম যেটা একটা `cmp` comparator নেয় — min-heap-এর জন্য `(a,b)=>a-b`, max-heap-এর জন্য `(a,b)=>b-a`। এতে Python-এর "max-heap-এর জন্য value negate করা" hack লাগে না; comparator উল্টে দিলেই হয়, যা বেশি পরিষ্কার। median জোড় হলে `/2` (integer division নয়), তাই 1.5-এর মতো float ঠিক আসে।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
class Heap {
private a: number[] = [];
constructor(private cmp: (a: number, b: number) => number) {}
get size(): number { return this.a.length; }
peek(): number { return this.a[0]; }
push(x: number): void {
const a = this.a, c = this.cmp; a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (c(a[p], a[i]) <= 0) break;
[a[p], a[i]] = [a[i], a[p]]; i = p;
}
}
pop(): number {
const a = this.a, c = this.cmp, top = a[0], last = a.pop() as number;
if (a.length) {
a[0] = last; let i = 0;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2; let best = i;
if (l < a.length && c(a[l], a[best]) < 0) best = l;
if (r < a.length && c(a[r], a[best]) < 0) best = r;
if (best === i) break;
[a[best], a[i]] = [a[i], a[best]]; i = best;
}
}
return top;
}
}
class MedianFinder {
private lower = new Heap((a, b) => b - a); // max-heap (ছোট অর্ধ)
private upper = new Heap((a, b) => a - b); // min-heap (বড় অর্ধ)
addNum(num: number): void {
this.lower.push(num);
this.upper.push(this.lower.pop());
if (this.upper.size > this.lower.size) this.lower.push(this.upper.pop());
}
findMedian(): number {
if (this.lower.size > this.upper.size) return this.lower.peek();
return (this.lower.peek() + this.upper.peek()) / 2;
}
}
const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const mf = new MedianFinder();
mf.addNum(1); mf.addNum(2);
expect(mf.findMedian() === 1.5, "1.5");
mf.addNum(3);
expect(mf.findMedian() === 2, "2");
const mf2 = new MedianFinder();
for (const x of [5, 2, 8, 1]) mf2.addNum(x);
expect(mf2.findMedian() === 3.5, "3.5");
const mf3 = new MedianFinder();
mf3.addNum(4);
expect(mf3.findMedian() === 4, "একক");
const mf4 = new MedianFinder();
for (const x of [-1, -2, -3]) mf4.addNum(x);
expect(mf4.findMedian() === -2, "-2");
console.log("সব TS test pass!");
```
> **TS টীকা:** `private lower` ও `private upper` দুই heap-কে class-এর ভেতরে আটকে রাখে — বাইরে থেকে partition ভাঙা যায় না, invariant সুরক্ষিত। `addNum(num: number)` ও `findMedian(): number` signature স্পষ্ট করে contract। comparator `(a, b) => number` typed হওয়ায় ভুল comparator (যেমন boolean ফেরত) compile-time-এই ধরা পড়ে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
`addNum` **O(log n)** — কয়েকটা constant-সংখ্যক push/pop, প্রতিটা O(log n)। `findMedian` **O(1)** — শুধু দুই top peek। n insert-এর জন্য মোট O(n log n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — সব সংখ্যা দুই heap-এ মিলে জমা থাকে। মাঝপথে কিছু ফেলা হয় না, তাই memory stream-এর সমানুপাতিক।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `lower`-কে max-heap না বানিয়ে সরাসরি heapq ব্যবহার — তখন partition উল্টে যায়, median ভুল।
- balance ভুলে যাওয়া বা ভুল দিকে করা — দুই heap-এর size পার্থক্য 1-এর বেশি হলে median ভুল।
- জোড়/বিজোড় case গুলিয়ে ফেলা — invariant অনুযায়ী lower বড় হলে median = lower top; সমান হলে গড়।
- integer division ব্যবহার করা (`/` এর বদলে `//` বা int) — median float হতে পারে (যেমন 1.5)।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `08`-এর `concept.md`-র max-heap-via-negation আর `patterns.md`-র Pattern 3 (Two heaps for running median) — "lower half max-heap + upper half min-heap, balanced রাখো, median দুই top-এ"। `MedianFinder`-এর reference implementation-ও সেখানকার `implementation.py`-তে আছে।
### পরের অনুশীলন {#22-similar-harder-problems}
- Sliding Window Median —