018 — Find Median from Data Stream

Source

• Original source: Classic running-median via two balanced heaps
• Platform: LeetCode — https://leetcode.com/problems/find-median-from-data-stream/
• 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

1. Problem in simple words

একটা data stream থেকে এক এক করে সংখ্যা আসছে। তোমাকে একটা structure বানাতে হবে যেটা দুটো কাজ করে: addNum(x) — stream-এ একটা নতুন সংখ্যা যোগ করা, আর findMedian() — এখন পর্যন্ত দেখা সব সংখ্যার median ফেরত দেওয়া। সংখ্যা জোড় হলে median = মাঝের দুটোর গড়; বিজোড় হলে ঠিক মাঝেরটা।

addNum(1); addNum(2)        -> findMedian() = 1.5
addNum(3)                   -> findMedian() = 2

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) দরকারই পড়ে না।

6. Real-life analogy

ভাবো একটা দাঁড়িপাল্লা (seesaw), যার pivot-এ median। বাঁ পাল্লায় ছোট সংখ্যাগুলো, ডান পাল্লায় বড়গুলো। প্রতিটা heap শুধু তার ভেতরের কিনারাটা — মাঝখান ছুঁয়ে থাকা value-টা — দেখায়। দুই পাল্লা প্রায় সমান ভারী রাখো (পার্থক্য বড়জোর 1), তাহলে মাঝখানের value(s) সবসময় হাতের নাগালে; সেটাই median।

7. Visual explanation

5, 2, 8, 1 যোগ করার পর — lower max-heap (ছোট অর্ধ), upper min-heap (বড় অর্ধ):

   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)

8. Example input and output

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   (একটাই সংখ্যা)

9. Brute force thinking

প্রথম সরল চিন্তা: সব সংখ্যা একটা list-এ জমাও। findMedian ডাকলে list-টা sort করো, তারপর মাঝের element (বা দুটোর গড়) নাও।

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)-এর কথা মাথায় আসা উচিত।

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

15. Python solution

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-এর গড়।

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!।

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)।

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 — https://leetcode.com/problems/sliding-window-median/ (এই tracker-এর #21; two heaps + lazy deletion)
• IPO — https://leetcode.com/problems/ipo/ (#19; two heaps, কিন্তু affordable vs not-yet-affordable split)
• Sliding Window Maximum — https://leetcode.com/problems/sliding-window-maximum/ (#16; window + heap, lazy deletion)

23. Pattern learned

Two heaps: numbers-কে lower half (max-heap) আর upper half (min-heap)-এ ভাগ করো, size প্রায় সমান রাখো; median সবসময় দুই top-এ। "running/window median বা দুই অর্ধ balance" দরকার পড়লেই এই seesaw-ছবি মনে করো — insert O(log n), median O(1)।

24. Final summary

ভবিষ্যতের আমাকে: "stream-এর running median" = দুই heap (lower max-heap negate করা, upper min-heap), insert-এ partition + balance, median দুই top থেকে। invariant — lower ≥ upper, পার্থক্য বড়জোর 1। Sliding Window Median-এ এর সাথে lazy deletion যোগ হবে; base এখানে শিখে রাখলে সেটা সহজ।

25. JavaScript solution (with test cases)

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 ঠিক আসে।

26. TypeScript solution (with test cases)

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-এই ধরা পড়ে।

27. কোথায় কাজে লাগে (real-world use)

• Real-time analytics dashboard: চলমান metric-stream (latency, response time, দাম) থেকে running median দেখানো — average-এর চেয়ে outlier-resistant।
• Sensor / IoT data: ধারাবাহিক sensor রিডিং-এর median track করা (spike-এ কম প্রভাবিত), anomaly detection-এ।
• Financial / market data: ট্রেড দামের running median বা percentile maintain করা — risk আর fair-value estimation-এ।
• Load balancing / SLA monitoring: চলমান request-time-এর median/percentile দেখে কখন scaling দরকার তা সিদ্ধান্ত নেওয়া।
• Online statistics: যেকোনো জায়গায় যেখানে data এক এক করে আসে আর প্রতি মুহূর্তে "মাঝের মান" দরকার, পুরো ইতিহাস বারবার sort না করে।

মূল সুর: stream/window-এ running median বা দুই অর্ধ balance করতে হলে two-heaps (lower max + upper min) — insert O(log n), median query O(1)।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।