101 — Median of Two Sorted Arrays

এই level-এর সবচেয়ে বিখ্যাত (আর ভয় পাওয়া) problem-গুলোর একটা। কিন্তু ভয়টা অমূলক — যদি তুমি একটা সুন্দর কোণ থেকে দেখো। আমরা দুটো array জোড়া দিয়ে sort করব না; বরং একটা ছোট "কোথায় কাটব" প্রশ্নকে binary search দিয়ে সমাধান করব। এই note-এ আসল লক্ষ্য answer মুখস্থ নয় — partition নামের একটা শক্তিশালী চিন্তার সাথে পরিচয়, যা 092-এর lower bound চিন্তারই গভীর রূপ।

Source

• Original source: LeetCode — Median of Two Sorted Arrays
• Platform: LeetCode — https://leetcode.com/problems/median-of-two-sorted-arrays/
• Topic: Math-based programming fundamentals → Level 7: Binary Search on Answer
• Difficulty: Hard
• Pattern: partition search (দুই array-কে এক জায়গায় কেটে বাঁ-অর্ধ ও ডান-অর্ধ সাজানো)
• Basic idea inherited from: 092 — Lower Bound

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-এর আসল উদ্দেশ্য আরও চালাক কিছু শেখা।

2. What is the math idea?

মূল ধারণা — partition (বিভাজন)। মিলিত sorted array-র median আসলে একটা প্রশ্ন: পুরো জিনিসটাকে ঠিক মাঝখানে এমনভাবে দুই ভাগে (বাঁ অর্ধ + ডান অর্ধ) কাটো যাতে (ক) দুই অর্ধে সমান (বা বাঁ-এ এক বেশি) উপাদান থাকে, আর (খ) বাঁ অর্ধের সবচেয়ে বড় উপাদান ≤ ডান অর্ধের সবচেয়ে ছোট উপাদান।

চমৎকার ব্যাপার — এই কাটাটা পুরোপুরি ঠিক হয়ে যায় শুধু প্রথম array-তে কোথায় কাটব সেটা বেছে নিলেই; কারণ মোট বাঁ-অর্ধে কতগুলো উপাদান লাগবে তা স্থির, তাই a-তে iটা নিলে b-তে বাকি half − iটা আপনাআপনি ঠিক হয়। আর "সঠিক কাটা"-র শর্ত i-এর সাথে monotonic — তাই i খুঁজতে binary search। এটাই BSoA-র partition রূপ।

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-এর সিঁড়ি হয়ে ফিরবে।

4. Real-life analogy

ভাবো দুটো আলাদা লাইনে দাঁড়ানো লোক, প্রতিটা লাইন উচ্চতা অনুযায়ী সাজানো (সামনে বেঁটে, পিছনে লম্বা)। তুমি দুটো লাইনকেই ঠিক মাঝবরাবর একটা করে দড়ি দিয়ে দুই টুকরো করতে চাও — সব "সামনের" অংশ এক দিকে, সব "পিছনের" অংশ আরেক দিকে।

শর্ত: দুই লাইন মিলিয়ে সামনের দলে আর পিছনের দলে সমান লোক থাকুক, আর সামনের দলের সবচেয়ে লম্বা লোকও পিছনের দলের সবচেয়ে বেঁটে লোকের চেয়ে বেঁটে (বা সমান) হোক। তুমি প্রথম লাইনে দড়িটা একটু এদিক-ওদিক সরিয়ে দেখছ — বেশি লোক সামনে পড়ে গেলে দড়ি পিছাও, কম পড়লে এগোও। দ্বিতীয় লাইনের দড়ি আপনাআপনি ঠিক হয়ে যায় (কারণ মোট সামনের সংখ্যা স্থির)। ঠিক জায়গায় দড়ি পড়লে — সীমানার চার জন (দুই দিকের শেষ/প্রথম) দেখে median বলে দেওয়া যায়।

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:

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 স্থির):

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।

6. Example input and output

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-সীমা সহজ থাকে।

7. Brute force thinking

সবচেয়ে সরল চিন্তা — দুটো array জুড়ে দাও, পুরোটা sort করো, তারপর মাঝের মান(গুলো) পড়ো:

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 করছি, এটাই অপচয়।

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 আপনাআপনি বসে যায়:

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 চিন্তাটা মাথায় আসুক।

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-এর সাথে মিলল।

12. Python solution

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

if len(a) > len(b): a, b = b, a

সবসময় ছোট array-তে binary search চালাই — তাহলে i-এর সীমা [0, m] ছোট থাকে, আর জটিলতা O(log(min(m,n)))-এ নামে।

half = (m + n + 1) // 2

বাঁ অর্ধে কতগুলো উপাদান যাবে। +1 দিয়ে integer ভাগ করায় বিজোড় মোট হলে বাঁ-এ এক বেশি পড়ে — তাই median সবসময় max(aL, bL) (বাঁ-অর্ধের শেষ) থেকে পাওয়া যায়, আলাদা কেস কমে।

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 পুরো এক দিকে) ঝামেলাহীন করে।

if aL <= bR and bL <= aR:

বৈধ partition-এর সংজ্ঞা: বাঁ-অর্ধের প্রতিটি ≤ ডান-অর্ধের প্রতিটি — যা নিশ্চিত হয় শুধু সীমানা চেক করলেই (aL ≤ bR আর bL ≤ aR)। বৈধ হলে median বের করি (বিজোড় → max বাঁ; জোড় → max বাঁ ও min ডান-এর গড়)।

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

14. Output walkthrough

চালালে যা ছাপবে:

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-এর সাথে মিলেছে।

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 হবে।

18. Harder problems that inherit this idea

• LeetCode — Kth Smallest Element in a Sorted Matrix (https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/) — sorted গঠনে binary search + counting, partition-চিন্তার আত্মীয়।
• LeetCode — Find K-th Smallest Pair Distance (https://leetcode.com/problems/find-k-th-smallest-pair-distance/) — উত্তরের উপর binary search + count ≤ x।
• 102 (Kth Smallest in Multiplication Table) — এই repo-রই পরের ধাপ; "k-th মান খুঁজতে count-এর উপর binary search" একই দর্শন।

19. Pattern learned

Partition search (binary search on the cut) — দুই sorted জিনিসকে এমন এক জায়গায় কাটো যাতে বাঁ-অর্ধ সবটাই ≤ ডান-অর্ধ; এক array-তে কাটার জায়গা i binary search করো, অন্যটার j আপনাআপনি বসে। বড় শিক্ষা: median/মাঝ খুঁজতে পুরোটা merge না করে শুধু "সঠিক কাটা" খোঁজো — সীমানার চারটে সংখ্যাই উত্তর দেয়, আর কাটা-বৈধতা monotonic বলে binary search চলে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "Median of Two Sorted = partition search; ছোট array-তে কাটা i খুঁজি (j = half − i), aL ≤ bR ও bL ≤ aR হলে বৈধ — বিজোড়ে max(aL,bL), জোড়ে (max বাঁ + min ডান)/2। Signal: 'two sorted arrays' + 'O(log)' দেখলেই merge ভুলে partition ভাবো; ±INF দিয়ে প্রান্ত সামলাই।"

পরের ধাপ → 102 — Kth Smallest in Multiplication Table (উত্তরের উপর binary search + counting)। ভিত্তি → 092 — Lower Bound। সম্পর্কিত → 100 — Split Array Largest Sum।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

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