026 — Median of Two Sorted Arrays

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• Original source: Classic capstone interview problem (median via partition binary search)
• Platform: LeetCode — https://leetcode.com/problems/median-of-two-sorted-arrays/
• Topic: binary search + arrays + math invariants
• Difficulty: Hard
• Pattern: binary search on a partition (একটা partition খুঁজে median বের করা)
• Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে binary search (math level 07) (partition-এর উপর search), 02 arrays (দুই sorted array নিয়ে কাজ), আর 01 math-এর invariant চিন্তা (left-half size আর max-left ≤ min-right শর্ত)। তিন tool মিলে O(log(min(m,n)))।

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে দুটো sorted integer array a আর b দেওয়া আছে। দুটোকে একসাথে মিলিয়ে একটা বড় sorted array কল্পনা করো; তার median (মাঝের মান, জোড় হলে মাঝের দুটোর গড়) বের করো।

শর্ত: পুরো merge না করে, time complexity রাখতে হবে O(log(m+n)) — অর্থাৎ সরাসরি জোড়া লাগানো (O(m+n)) যথেষ্ট ভালো নয়, binary search-ভিত্তিক সমাধান চাই।

উদাহরণ

a = [1, 3],  b = [2]
merged = [1, 2, 3]  -> median = 2

a = [1, 2],  b = [3, 4]
merged = [1, 2, 3, 4]  -> median = (2 + 3) / 2 = 2.5

Input ও output

উদাহরণ

a = [1, 3], b = [2]          -> 2.0        (বিজোড় মোট, মাঝের একটা)
a = [1, 2], b = [3, 4]       -> 2.5        (জোড় মোট, মাঝের দুটোর গড়)
a = [], b = [1]              -> 1.0        (একটা array খালি)
a = [0, 0], b = [0, 0]       -> 0.0
a = [1, 3, 8], b = [7, 9, 10, 11] -> 8.0

চেনা উদাহরণে বোঝা

ভাবো দুটো আলাদা সারিতে উচ্চতা-অনুযায়ী দাঁড়ানো দুই দল লোক, প্রতিটা সারি নিজে নিজে sorted। তুমি দুই সারিতে একটা করে "কাঁচি দিয়ে কাটা দাগ" বসাতে চাও, যাতে দুই দাগের বাঁ পাশে মিলে ঠিক অর্ধেক লোক থাকে, আর বাঁ পাশের সবাই ডান পাশের সবার চেয়ে বেঁটে।

দাগ ঠিক জায়গায় বসলে, মাঝের মান চারটে সীমান্ত-লোকের মধ্যেই — পুরো দুই সারি মিশিয়ে গুনতে হয় না। ভুল হলে এক সারির দাগ একটু সরাও, আর binary search-এর মতো দ্রুত ঠিক জায়গায় পৌঁছাও।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এই problem তিনটা আগের ধারণা জোড়া দেয়:

• binary search (math level 07) থেকে: উত্তরটা নিজে array-তে নেই — আমরা একটা partition position-এর উপর binary search করি (search-on-answer-এর আত্মীয়)।
• 02 arrays থেকে: দুটো sorted array-র index নিয়ে boundary element তুলনা।
• 01 math-এর invariant থেকে: সঠিক partition-এর দুটো নিয়ম — বাঁ অর্ধেকে ঠিক অর্ধেক element, আর "বাঁয়ের সব ≤ ডানের সব"।

একা binary search দেয় log-time search; একা arrays দেয় boundary তুলনা; invariant বলে দেয় কোন দিকে search সরাতে হবে। তিন মিলে O(log(min(m,n)))।

ভেতরের যুক্তি

লুকানো logic একটা partition invariant: ছোট array-তে একটা cut i বাছো, আর বড় array-তে cut j এমন করো যাতে দুই array-র বাঁ অংশ মিলে মোট element-এর ঠিক অর্ধেক (i + j = (m + n + 1) // 2)।

Partition সঠিক যখন: a[i-1] <= b[j] এবং b[j-1] <= a[i] — অর্থাৎ বাঁ অর্ধেকের সর্বোচ্চ ≤ ডান অর্ধেকের সর্বনিম্ন। তখন median এই চারটে boundary element থেকেই বেরোয়।

কী দিয়ে তথ্য রাখব

কোনো বড় data structure লাগে না — শুধু দুটো sorted array-র index (cut position) আর কয়েকটা boundary value। সমাধান শুধু ছোট array-র cut position-এর উপর binary search চালায় (O(log(min(m,n)))); বড় array-র cut গণিত দিয়ে derive হয়।

এটি কেন উপযুক্ত

পুরো merge করলে O(m+n) — শর্ত ভাঙে। আমরা চাই উত্তরের অবস্থান (partition) খুঁজে নিতে, value scan করে নয় — ঠিক binary search (03) যা করে, কিন্তু array-element-এর উপর নয়, cut position-এর উপর।

ছোট array-তে search চালানোই efficient: search space min(m, n), তাই খুব unbalanced size-এও দ্রুত। invariant (01) নিশ্চিত করে প্রতিটা ভুল cut থেকে কোন দিকে যেতে হবে সেটা একটামাত্র তুলনাতেই জানা যায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: দুটো array merge করে একটা বড় sorted array বানাও (two-pointer merge), তারপর মাঝের element (বা মাঝের দুটোর গড়) নাও।

উদাহরণ

merged = merge(a, b)          # two-pointer, O(m+n)
mid = len(merged) // 2
median = merged[mid] if odd else (merged[mid-1]+merged[mid]) / 2

কোথায় বেশি কাজ হচ্ছে

Merge পুরো m + n-টা element ছোঁয় — O(m+n) time আর O(m+n) space। problem-এর শর্ত O(log(m+n)) চায়, তাই এটা গৃহীত নয়। কারণ আমরা সব element merge করছি যখন কিনা median-এর জন্য শুধু সঠিক partition-টা জানলেই চলত — binary search (03) সেটাই সরাসরি খোঁজে।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: median-কে merge করে নয়, একটা সঠিক partition দিয়ে সংজ্ঞায়িত করা যায় — বাঁ অর্ধেকে ঠিক অর্ধেক element, আর বাঁয়ের সব ≤ ডানের সব। যেহেতু দুই array sorted, একটা cut সরালে boundary-গুলো monotonic-ভাবে বদলায় — তাই কোন দিকে সরাতে হবে তা একটা তুলনাতেই জানা যায়, আর binary search চলে।

আরও কম কাজে সমাধান

ছোট array-তে cut i-র উপর binary search করো; বড় array-র cut j = (m+n+1)//2 - i গণিতে বের করো। চারটে boundary নাও: aLeft=a[i-1], aRight=a[i], bLeft=b[j-1], bRight=b[j] (প্রান্তে -inf/+inf)।

• aLeft <= bRight এবং bLeft <= aRight → সঠিক cut; median বের করো।
• aLeft > bRight → i বড়, বাঁয়ে সরাও (hi = i - 1)।
• নাহলে → i ছোট, ডানে সরাও (lo = i + 1)।

ভাবনার পরিবর্তন

মোচড়: "দুই array merge করে মাঝখানে যাব" ভাবার বদলে ভাবো "এমন একটা cut খুঁজব যেখানে বাঁ অর্ধেক = অর্ধেক element আর বাঁয়ের সব ≤ ডানের সব।" O(m+n) merge একটা O(log(min(m,n))) partition-search-এ গুটিয়ে যায়।

ছবিতে বোঝা

a = [1,3,8,9,15], b = [7,11,18,19,21,25]। মোট 11টি সংখ্যা, তাই বাঁ অংশে half = 6টি রাখব। a-তে iটি নিলে b থেকে নিতে হবে j = 6-iটি।

উদাহরণ

শুরু: low=0, high=5
ধাপ 1: i=(0+5)//2=2, j=4
  a: [1,3]       | [8,9,15]
  b: [7,11,18,19]| [21,25]
  aLeft=3, aRight=8; bLeft=19, bRight=21
  bLeft > aRight: b থেকে বেশি নেওয়া হয়েছে, a থেকে কম।
  তাই a-র cut ডানে: low=i+1=3।

ধাপ 2: i=(3+5)//2=4, j=2
  a: [1,3,8,9] | [15]
  b: [7,11]    | [18,19,21,25]
  aLeft=9 <= bRight=18 এবং bLeft=11 <= aRight=15
  দুই শর্তই ঠিক। median=max(9,11)=11।

যাচাই: merged=[1,3,7,8,9,11,15,18,19,21,25]
                       মাঝের (ষষ্ঠ) সংখ্যা 11

দিক বাছার নিয়মটি নির্দিষ্ট: aLeft > bRight হলে i কমান; bLeft > aRight হলে i বাড়ান। শুধু “বাঁ অংশের সর্বোচ্চ বড়” জানলে কোন array-র cut সরাতে হবে বোঝা যায় না।

ছোট input-এ ধাপে ধাপে

a = [1, 2], b = [3, 4] (m=2, n=2, half=(4+1)//2=2):

1. ছোট array a-তে search, lo=0, hi=2। i = 1, j = 2 - 1 = 1।
2. boundary: aLeft=a[0]=1, aRight=a[1]=2, bLeft=b[0]=3, bRight=b[1]=4।
3. aLeft(1) <= bRight(4)? হ্যাঁ। bLeft(3) <= aRight(2)? না → bLeft বড়, i ছোট, lo = 2।
4. i = 2, j = 0। aLeft=a[1]=2, aRight=+inf, bLeft=-inf, bRight=b[0]=3।
5. 2 <= 3 ✓ এবং -inf <= +inf ✓ → সঠিক। মোট জোড়: median = (max(aLeft,bLeft) + min(aRight,bRight)) / 2 = (max(2,-inf) + min(+inf,3)) / 2 = (2+3)/2 = 2.5। ✓

কোড ও ব্যাখ্যা

Python

Python

def median_two_sorted(a, b):
    """BINARY SEARCH on a PARTITION (03) + array boundaries (02) + invariant (01)।
    ছোট array-র cut-এর উপর search; বড় array-র cut গণিতে; median 4 boundary থেকে।
    O(log(min(m, n)))।"""
    if len(a) > len(b):                      # সবসময় ছোট array-তে search
        a, b = b, a
    m, n = len(a), len(b)
    half = (m + n + 1) // 2                   # বাঁ অর্ধেকে কত element
    lo, hi = 0, m                             # a-তে cut position
    INF = float('inf')
    while lo <= hi:
        i = (lo + hi) // 2                    # a-র cut
        j = half - i                          # b-র cut (invariant ধরে রাখে)
        a_left = a[i - 1] if i > 0 else -INF  # প্রান্তে sentinel
        a_right = a[i] if i < m else INF
        b_left = b[j - 1] if j > 0 else -INF
        b_right = b[j] if j < n else INF
        if a_left <= b_right and b_left <= a_right:   # সঠিক partition
            if (m + n) % 2 == 1:                      # বিজোড়: বাঁ অর্ধেকের max
                return float(max(a_left, b_left))
            return (max(a_left, b_left) + min(a_right, b_right)) / 2.0
        elif a_left > b_right:                # a-র বাঁয়ে বড় element -> বাঁয়ে সরাও
            hi = i - 1
        else:                                # ডানে সরাও
            lo = i + 1
    raise ValueError("inputs sorted নয়")     # পৌঁছানোর কথা নয়


def brute(a, b):
    # obviously-correct reference: merge করে মাঝখান
    merged = sorted(a + b)
    k = len(merged)
    if k == 0:
        raise ValueError("খালি")
    if k % 2 == 1:
        return float(merged[k // 2])
    return (merged[k // 2 - 1] + merged[k // 2]) / 2.0


# ---- tests ----
assert median_two_sorted([1, 3], [2]) == 2.0
assert median_two_sorted([1, 2], [3, 4]) == 2.5
assert median_two_sorted([], [1]) == 1.0
assert median_two_sorted([2], []) == 2.0
assert median_two_sorted([0, 0], [0, 0]) == 0.0
assert median_two_sorted([1, 3, 8], [7, 9, 10, 11]) == 8.0

# একটা array অন্যটার পুরো বাঁয়ে / ডানে
assert median_two_sorted([1, 2, 3], [4, 5, 6]) == 3.5
assert median_two_sorted([4, 5, 6], [1, 2, 3]) == 3.5

# random fuzz: partition-search vs merge-brute
import random
random.seed(26)
for _ in range(2000):
    m = random.randint(0, 8)
    n = random.randint(0, 8)
    if m + n == 0:
        continue
    a = sorted(random.randint(-15, 15) for _ in range(m))
    b = sorted(random.randint(-15, 15) for _ in range(n))
    got = median_two_sorted(a, b)
    exp = brute(a, b)
    assert abs(got - exp) < 1e-9, (a, b, got, exp)

print("সব test pass!")

কোডের প্রতিটি অংশ

• if len(a) > len(b): a, b = b, a — সবসময় ছোট array-তে search, তাই complexity O(log(min(m,n)))।
• half = (m + n + 1) // 2 — বাঁ অর্ধেকে কতগুলো element; +1 বিজোড় মোটকে বাঁ অর্ধেকে ফেলে।
• i, j — a-র cut binary-search-এ, b-র cut invariant i + j = half দিয়ে derived।
• চারটে boundary (a_left/a_right/b_left/b_right) — প্রান্তে ±inf sentinel দিয়ে edge handle।
• দুই invariant সঠিক হলে median ফেরে; নাহলে boundary তুলনা বলে কোন দিকে cut সরাবে।
• brute — merge-and-middle reference, fast version যাচাই করতে।

Output মিলিয়ে দেখা

[1,3] + [2] দেয় 2.0 (বিজোড়), [1,2] + [3,4] দেয় 2.5 (জোড়, মাঝের দুটোর গড়)। খালি array, সব-সমান, আর disjoint array সব সঠিক। শেষে 2000 random fuzz-এ partition-search merge-brute-এর সাথে মেলে (float tolerance-সহ)। শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(log(min(m, n))) — শুধু ছোট array-র cut position-এর উপর binary search; প্রতিটা step-এ O(1) boundary তুলনা।

অতিরিক্ত জায়গা

O(1) — কয়েকটা index আর boundary value; merge করা হয় না, তাই extra array লাগে না (brute-এর O(m+n) থেকে বড় উন্নতি)।

যে ভুলগুলো এড়াতে হবে

• বড় array-তে search চালানো — কাজ করবে, কিন্তু complexity O(log(max)) আর প্রান্ত-handling জটিল; ছোটটায় search করো।
• প্রান্তে ±inf sentinel না দেওয়া — i=0 বা i=m-এ index error বা ভুল তুলনা।
• half-এ +1 ভুলে যাওয়া — বিজোড় মোটে median-element ভুল অর্ধেকে পড়ে।
• জোড়/বিজোড় শাখা গুলিয়ে ফেলা — বিজোড়ে বাঁ অর্ধেকের max, জোড়ে দুই boundary-র গড়।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: binary search (binary search (math level 07), এখানে array-element নয়, partition position-এর উপর — search-on-answer পরিবার) + sorted-array boundary তুলনা (02 arrays) + partition invariant (01 math, left-size আর order শর্ত)। তিনটা cold-এ জানা থাকলে এই হার্ড সমাধান গড়ে ওঠে।

পরের অনুশীলন

• Kth Smallest Element in a Sorted Matrix (binary-search-on-value) — https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
• Split Array Largest Sum (search-on-answer) — https://leetcode.com/problems/split-array-largest-sum/
• Find K-th Smallest Pair Distance — https://leetcode.com/problems/find-k-th-smallest-pair-distance/

কৌশলটি মনে রাখুন

Binary search on a partition: উত্তরকে value scan করে নয়, একটা সঠিক cut দিয়ে সংজ্ঞায়িত করা — বাঁ অর্ধেক = অর্ধেক element আর বাঁয়ের সব ≤ ডানের সব — তারপর ছোট array-তে cut-এর উপর binary search। binary search + arrays + math-invariant-এর গভীরতম মেলবন্ধন।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "দুই sorted array-র median, sublinear time" দেখলেই partition binary search মনে করবে। ছোট array-তে cut i, বড়টায় j = half - i; চারটে boundary নাও (প্রান্তে ±inf); aLeft<=bRight && bLeft<=aRight হলে median বের করো, নাহলে boundary তুলনা দেখে cut সরাও। merge করো না — partition-ই যথেষ্ট, O(log(min(m,n)))।

---

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