Problem link ও উৎস
- **Original source:** LeetCode — Median of Two Sorted Arrays
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 7: Binary Search on Answer
- **Difficulty:** Hard
- **Pattern:** partition search (দুই array-কে এক জায়গায় কেটে বাঁ-অর্ধ ও ডান-অর্ধ সাজানো)
- **Basic idea inherited from:** 092 — Lower Bound
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো **আগে থেকেই sort করা** array `a` আর `b` দেওয়া। ভাবো এদের মিলিয়ে একটাই বড় sorted array বানালে — তার **median** (মাঝের মান) কত? সেটাই বের করতে হবে।
মনে করিয়ে দিই median কী: মোট উপাদান সংখ্যা বিজোড় হলে median = ঠিক মাঝের উপাদান; জোড় হলে median = মাঝের দুটো উপাদানের গড়। যেমন `[1, 3, 8]`-এর median 3, আর `[1, 3, 8, 9]`-এর median (3+8)/2 = 5.5।
আসল চ্যালেঞ্জ — আমরা চাই খুব দ্রুত, `O(log(min(m, n)))` সময়ে। মানে দুটো array মিশিয়ে sort করার (যা O((m+n) log(m+n))) সহজ রাস্তা থাকলেও, এই problem-এর আসল উদ্দেশ্য আরও চালাক কিছু শেখা।
### Input ও output {#6-example-input-and-output}
```text
a b output কেন
-----------------------------------------------------------
[1, 3] [2] 2.0 মিলিত [1,2,3], মাঝে 2
[1, 2] [3, 4] 2.5 মিলিত [1,2,3,4], (2+3)/2
[] [1] 1.0 এক array খালি
[] [2, 3] 2.5 খালি + জোড়
[0, 0] [0, 0] 0.0 সব সমান
[1, 3, 8] [7, 9, 10, 11] 8.0 মিলিত মাঝে 8
```
মূল edge case: **একটা array খালি** (তখন অন্যটার median-ই উত্তর), **সব উপাদান সমান**, আর মোট সংখ্যা **জোড় বনাম বিজোড়** (জোড়ে দুটো মাঝের মানের গড়)। সবসময় ছোট array-তে binary search চালালে index-সীমা সহজ থাকে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো দুটো আলাদা লাইনে দাঁড়ানো লোক, প্রতিটা লাইন উচ্চতা অনুযায়ী সাজানো (সামনে বেঁটে, পিছনে লম্বা)। তুমি দুটো লাইনকেই ঠিক মাঝবরাবর একটা করে দড়ি দিয়ে দুই টুকরো করতে চাও — সব "সামনের" অংশ এক দিকে, সব "পিছনের" অংশ আরেক দিকে।
শর্ত: দুই লাইন মিলিয়ে সামনের দলে আর পিছনের দলে সমান লোক থাকুক, আর সামনের দলের সবচেয়ে লম্বা লোকও পিছনের দলের সবচেয়ে বেঁটে লোকের চেয়ে বেঁটে (বা সমান) হোক। তুমি প্রথম লাইনে দড়িটা একটু এদিক-ওদিক সরিয়ে দেখছ — বেশি লোক সামনে পড়ে গেলে দড়ি পিছাও, কম পড়লে এগোও। দ্বিতীয় লাইনের দড়ি আপনাআপনি ঠিক হয়ে যায় (কারণ মোট সামনের সংখ্যা স্থির)। ঠিক জায়গায় দড়ি পড়লে — সীমানার চার জন (দুই দিকের শেষ/প্রথম) দেখে median বলে দেওয়া যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **092 — Lower Bound**-এর উপর। 092-এ তুমি শিখেছিলে "প্রথম এমন জায়গা খোঁজা যেখান থেকে একটা শর্ত True হয়ে যায়" — অর্থাৎ একটা monotonic predicate-এর সীমানা binary search দিয়ে ধরা। এখানে predicate-টা হলো "`a`-তে `i`টা নিলে কি কাটা বৈধ (বা বেশি বাঁদিকে গেছে)?" — সেই সীমানাই median-এর সঠিক কাটা।
মানে নতুন কিছু আবিষ্কার করছি না — 092-এর "monotonic শর্তের প্রথম True খোঁজা" চিন্তাটাকেই একটা জ্যামিতিক (কোথায় কাটব) প্রশ্নে লাগাচ্ছি। তাই আটকে গেলে 092-এ ফিরে দেখো; lower bound-এর সিঁড়ির ছবিটাই এখানে partition-এর সিঁড়ি হয়ে ফিরবে।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল ধারণা — **partition (বিভাজন)**। মিলিত sorted array-র median আসলে একটা প্রশ্ন: পুরো জিনিসটাকে ঠিক মাঝখানে এমনভাবে দুই ভাগে (বাঁ অর্ধ + ডান অর্ধ) কাটো যাতে (ক) দুই অর্ধে সমান (বা বাঁ-এ এক বেশি) উপাদান থাকে, আর (খ) **বাঁ অর্ধের সবচেয়ে বড় উপাদান ≤ ডান অর্ধের সবচেয়ে ছোট উপাদান**।
চমৎকার ব্যাপার — এই কাটাটা পুরোপুরি ঠিক হয়ে যায় শুধু **প্রথম array-তে কোথায় কাটব** সেটা বেছে নিলেই; কারণ মোট বাঁ-অর্ধে কতগুলো উপাদান লাগবে তা স্থির, তাই `a`-তে `i`টা নিলে `b`-তে বাকি `half − i`টা আপনাআপনি ঠিক হয়। আর "সঠিক কাটা"-র শর্ত `i`-এর সাথে **monotonic** — তাই `i` খুঁজতে binary search। এটাই BSoA-র partition রূপ।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল চিন্তা — দুটো array জুড়ে দাও, পুরোটা sort করো, তারপর মাঝের মান(গুলো) পড়ো:
```python
def median_brute(a, b):
merged = sorted(a + b) # দুই array জুড়ে sort
n = len(merged)
if n == 0:
raise ValueError("empty")
mid = n // 2
if n % 2 == 1:
return float(merged[mid])
return (merged[mid - 1] + merged[mid]) / 2
```
এটা একদম সোজা আর নিশ্চিত ঠিক — তাই আমাদের asserts-এ এটাই reference হিসেবে কাজে লাগবে। ছোট input-এ চমৎকার, পড়তেও সহজ।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
জোড়া array `(a + b)` বানানো O(m + n), আর sort করা O((m + n) log(m + n))। দুটো array ইতিমধ্যেই sorted — সেই মূল্যবান তথ্যটা আমরা ফেলে দিয়ে আবার শূন্য থেকে sort করছি, এটাই অপচয়।
```text
m + n = 2,000,000 হলে:
brute (sort): ~2e6 × log2(2e6) ≈ 4.2 কোটি তুলনা (ধীর)
partition BSoA: ~log2(1e6) ≈ 20 ধাপ (চোখের নিমেষে)
```
(একটা মাঝারি রাস্তাও আছে — দুই pointer দিয়ে merge করতে করতে মাঝ পর্যন্ত যাওয়া, O(m + n)। কাজ করে, কিন্তু target `O(log(min(m,n)))` ছোঁয় না।) আসল লক্ষ্য — sorted ধর্মটা কাজে লাগিয়ে log সময়ে নামা।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — পুরো জিনিস merge না করে শুধু **সঠিক partition** খুঁজি। ছোট array-তে (ধরো `a`) binary search চালিয়ে `i` ঠিক করি; `b`-তে `j = half − i` আপনাআপনি বসে যায়:
```python
def find_median(a, b):
if len(a) > len(b): # ছোটটায় search — index সীমা সহজ
a, b = b, a
m, n = len(a), len(b)
half = (m + n + 1) // 2 # বাঁ অর্ধে কতগুলো (বিজোড়ে এক বেশি বাঁয়ে)
lo, hi = 0, m
INF = float('inf')
while lo <= hi:
i = (lo + hi) // 2 # a-তে বাঁয়ে i টা
j = half - i # b-তে বাঁয়ে j টা
aL = a[i - 1] if i > 0 else -INF
aR = a[i] if i < m else INF
bL = b[j - 1] if j > 0 else -INF
bR = b[j] if j < n else INF
if aL <= bR and bL <= aR: # সঠিক কাটা
if (m + n) % 2 == 1:
return float(max(aL, bL))
return (max(aL, bL) + min(aR, bR)) / 2
elif aL > bR: # a-তে বাঁয়ে বেশি নিয়েছি
hi = i - 1
else: # a-তে বাঁয়ে কম নিয়েছি
lo = i + 1
```
`a` ছোট হওয়ায় binary search `O(log(min(m, n)))`। `±INF` সীমানা সামলায় (i=0 মানে a-র বাঁয়ে কিছু নেই ইত্যাদি)।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **median খুঁজতে পুরো array লাগে না; শুধু সীমানার চারটে সংখ্যা (দুই দিকের শেষ ও প্রথম) লাগে। আর সেই সীমানা ঠিক করতে শুধু এক array-তে কাটার জায়গা `i` বেছে নিলেই হয়।**
কারণ মোট বাঁ-অর্ধের আকার (`half`) স্থির — তাই `a`-তে `i` ঠিক করলে `b`-র `j` বাধ্য হয়ে বসে যায়, দুটো আলাদা করে খোঁজার দরকার নেই। আর "কাটা বৈধ কিনা" শর্তটা `i`-এর সাথে monotonic, তাই binary search এক ঝটকায় সঠিক `i` এনে দেয়। "দুই sorted জিনিসের মাঝ" দেখলেই এই partition + এক-দিকে-search চিন্তাটা মাথায় আসুক।
### ছবিতে বোঝা {#5-visual-explanation}
`a = [1, 3, 8, 9, 15]` (m=5), `b = [7, 11, 18, 19, 21, 25]` (n=6)। মোট 11 (বিজোড়), বাঁ-অর্ধে লাগবে `(11+1)//2 = 6`টা। `a`-তে `i` কাটি, `b`-তে `j = 6 − i`:
```text
a: 1 3 8 | 9 15 i=3 কাটা (বাঁয়ে 3টা: 1,3,8)
b: 7 11 | 18 19 21 25 j=6-3=3 কাটা (বাঁয়ে 3টা: 7,11)... না, 3টা: 7,11,18
বাঁ অর্ধ : { 1, 3, 8 } ∪ { 7, 11, 18 } -> max বাঁ = max(8, 18) = 18
ডান অর্ধ: { 9, 15 } ∪ { 19, 21, 25 } -> min ডান = min(9, 19) = 9
শর্ত check: aL=8 ≤ bR=19? হ্যাঁ। bL=18 ≤ aR=9? না! (18 > 9)
-> বাঁয়ে b বেশি নিয়েছি / a কম -> a-তে আরও বাঁদিকে নিতে হবে... আসলে i বাড়াও
```
i সরিয়ে সঠিক কাটায় পৌঁছানোর সিঁড়ি (predicate "aL ≤ bR" — i বাড়লে aL বাড়ে, bR বাড়ে, একসময় True স্থির):
```text
i: 0 1 2 3 4 5
aL≤bR : T T T F F F (এক ধরনের শর্ত)
bL≤aR : F F T T T T (উল্টোটা)
^
দুটো একসাথে সত্যি যেখানে = সঠিক কাটা
```
দুই শর্ত (`aL ≤ bR` এবং `bL ≤ aR`) একসাথে সত্যি হলেই কাটা ঠিক — তখন বিজোড়ে median = `max(aL, bL)`, জোড়ে = `(max(aL,bL) + min(aR,bR)) / 2`।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`a = [1, 2]`, `b = [3, 4]` (m=2, n=2, মোট 4 জোড়)। `half = (4+1)//2 = 2`। `lo=0, hi=2`:
| lo | hi | i=(lo+hi)//2 | j=half−i | aL | aR | bL | bR | aL≤bR ও bL≤aR? | সিদ্ধান্ত |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 2 | 1 | 1 | a[0]=1 | a[1]=2 | b[0]=3 | b[1]=4 | 1≤4 ✓, কিন্তু 3≤2 ✗ | bL>aR → lo = i+1 = 2 |
| 2 | 2 | 2 | 0 | a[1]=2 | +INF | −INF | b[0]=3 | 2≤3 ✓, −INF≤+INF ✓ | সঠিক কাটা! |
সঠিক কাটায় `i=2, j=0`: বাঁ অর্ধ = `{1, 2} ∪ {} = {1,2}`, ডান অর্ধ = `{} ∪ {3,4} = {3,4}`। মোট জোড় → median = `(max(aL,bL) + min(aR,bR)) / 2 = (max(2,−INF) + min(INF,3))/2 = (2 + 3)/2 = 2.5`। brute force-এর সাথে মিলল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def find_median(a, b):
"""দুই sorted array-র মিলিত median। O(log(min(len(a), len(b))))।"""
if len(a) > len(b): # সবসময় ছোটটায় search
a, b = b, a
m, n = len(a), len(b)
if m + n == 0:
raise ValueError("দুটো array-ই খালি")
half = (m + n + 1) // 2 # বাঁ অর্ধের আকার (বিজোড়ে এক বেশি বাঁয়ে)
INF = float('inf')
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # a-তে বাঁয়ে i টা
j = half - i # b-তে বাঁয়ে j টা
aL = a[i - 1] if i > 0 else -INF
aR = a[i] if i < m else INF
bL = b[j - 1] if j > 0 else -INF
bR = b[j] if j < n else INF
if aL <= bR and bL <= aR: # বৈধ partition
if (m + n) % 2 == 1:
return float(max(aL, bL))
return (max(aL, bL) + min(aR, bR)) / 2
elif aL > bR: # a-তে বাঁয়ে বেশি -> i কমাও
hi = i - 1
else: # a-তে বাঁয়ে কম -> i বাড়াও
lo = i + 1
raise RuntimeError("unreachable")
def median_brute(a, b):
"""জুড়ে sort করে median — reference।"""
merged = sorted(a + b)
k = len(merged)
mid = k // 2
if k % 2 == 1:
return float(merged[mid])
return (merged[mid - 1] + merged[mid]) / 2
# --- হাতে বাছা test ---
assert find_median([1, 3], [2]) == 2.0
assert find_median([1, 2], [3, 4]) == 2.5
assert find_median([], [1]) == 1.0
assert find_median([], [2, 3]) == 2.5
assert find_median([0, 0], [0, 0]) == 0.0
assert find_median([1, 3, 8], [7, 9, 10, 11]) == 8.0
# --- brute force-এর সাথে cross-check (random sorted array) ---
import random
random.seed(42)
for _ in range(3000):
m = random.randint(0, 6)
n = random.randint(0, 6)
if m + n == 0:
continue # দুটোই খালি — সংজ্ঞাহীন, বাদ
a = sorted(random.randint(-10, 10) for _ in range(m))
b = sorted(random.randint(-10, 10) for _ in range(n))
got = find_median(a, b)
exp = median_brute(a, b)
assert abs(got - exp) < 1e-9, (a, b, got, exp)
print(find_median([1, 2], [3, 4])) # 2.5
print(find_median([1, 3, 8], [7, 9, 10, 11])) # 8.0
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if len(a) > len(b): a, b = b, a
```
সবসময় ছোট array-তে binary search চালাই — তাহলে `i`-এর সীমা `[0, m]` ছোট থাকে, আর জটিলতা `O(log(min(m,n)))`-এ নামে।
```text
half = (m + n + 1) // 2
```
বাঁ অর্ধে কতগুলো উপাদান যাবে। `+1` দিয়ে integer ভাগ করায় বিজোড় মোট হলে বাঁ-এ এক বেশি পড়ে — তাই median সবসময় `max(aL, bL)` (বাঁ-অর্ধের শেষ) থেকে পাওয়া যায়, আলাদা কেস কমে।
```text
aL = a[i-1] if i > 0 else -INF; aR = a[i] if i < m else INF
```
`i=0` মানে a-র বাঁয়ে কিছু নেই → বাঁ-সীমা `−∞` (যাতে তুলনায় ছোট থাকে)। `i=m` মানে a-র ডানে কিছু নেই → ডান-সীমা `+∞`। এই sentinel গুলো প্রান্ত-কেস (এক array পুরো এক দিকে) ঝামেলাহীন করে।
```text
if aL <= bR and bL <= aR:
```
বৈধ partition-এর সংজ্ঞা: বাঁ-অর্ধের প্রতিটি ≤ ডান-অর্ধের প্রতিটি — যা নিশ্চিত হয় শুধু সীমানা চেক করলেই (`aL ≤ bR` আর `bL ≤ aR`)। বৈধ হলে median বের করি (বিজোড় → max বাঁ; জোড় → max বাঁ ও min ডান-এর গড়)।
```text
elif aL > bR: hi = i - 1 else: lo = i + 1
```
`aL > bR` মানে a-তে বাঁয়ে বেশি নিয়েছি (বাঁ-অর্ধ খুব বড়) → `i` কমাও। নাহলে a-তে বাঁয়ে কম → `i` বাড়াও। এই দুই move-ই predicate-এর monotonicity ধরে — 092-এর lower bound চলনের আত্মীয়।
cross-check অংশে 3000টা random sorted জোড়ায় partition আর merge-sort মিলিয়ে দেখা (float তুলনায় `1e-9` সহনশীলতা) — সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
2.5
8.0
সব test pass!
```
প্রথম লাইন: `[1, 2]`, `[3, 4]` → dry run-এ পাওয়া 2.5। দ্বিতীয়: `[1, 3, 8]`, `[7, 9, 10, 11]` → মিলিত `[1,3,7,8,9,10,11]`, মাঝে (index 3) 8 → 8.0। তার আগের সব `assert` (হাতে বাছা + 3000টা random cross-check) চুপচাপ pass। সবশেষে `সব test pass!` — partition logic সব কেসে merge-sort-এর সাথে মিলেছে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(log(min(m, n)))** — ছোট array-তে binary search; প্রতি ধাপে ধ্রুবক কাজ (চারটে সীমা পড়া আর তুলনা)। তাই ধাপ সংখ্যা ছোট array-র দৈর্ঘ্যের log। (brute sort-এর O((m+n) log(m+n)) থেকে বিশাল লাফ; merge পথের O(m+n) থেকেও দ্রুত।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — কোনো merged array বানাচ্ছি না; শুধু `lo, hi, i, j` আর চারটে সীমা-variable। input ছাড়া স্মৃতি ধ্রুবক। (brute reference-এ `a + b` জোড়ায় O(m+n) লাগে, কিন্তু আসল সমাধান O(1)।)
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **ছোট array-তে search না করা** — বড়টায় চালালে `j = half − i` ঋণাত্মক হয়ে index ভেঙে যেতে পারে; তাই গোড়ায় swap করে `a` ছোট রাখো।
2. **সীমানায় `±INF` না বসানো** — `i=0` বা `i=m`-এ array-র বাইরে পড়লে IndexError; sentinel `−∞ / +∞` দিয়ে সামলাও।
3. **`half`-এ `+1` ভুলে যাওয়া** — `(m+n)//2` নিলে বিজোড় মোটে median-এর position বদলে যায়; `(m+n+1)//2` রাখলে বিজোড় ও জোড় দুটোই এক সূত্রে আসে।
4. **জোড়/বিজোড় গুলিয়ে ফেলা** — বিজোড়ে median = `max(aL, bL)`; জোড়ে = `(max(aL,bL) + min(aR,bR)) / 2`। দুটো আলাদা।
5. **integer ভাগ দিয়ে median** — জোড়ে গড় বের করতে `/` (float) ব্যবহার করো; `//` দিলে `2.5` ভুল করে `2` হবে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Kth Smallest Element in a Sorted Matrix** (