026 — Median of Two Sorted Arrays

Source

• 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 — এখানে মেশে 03 binary search (partition-এর উপর search), 02 arrays (দুই sorted array নিয়ে কাজ), আর 01 math-এর invariant চিন্তা (left-half size আর max-left ≤ min-right শর্ত)। তিন tool মিলে O(log(min(m,n)))।

1. Problem in simple words

তোমাকে দুটো 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

2. Which basic idea does this inherit from?

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

• 03 binary search থেকে: উত্তরটা নিজে 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)))।

3. What is the hidden math or logic?

লুকানো 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 থেকেই বেরোয়।

4. Which data structure is needed?

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

5. Why this data structure fits

পুরো 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 থেকে কোন দিকে যেতে হবে সেটা একটামাত্র তুলনাতেই জানা যায়।

6. Real-life analogy

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

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

7. Visual explanation

a = [1, 3, 8, 9, 15], b = [7, 11, 18, 19, 21, 25] (m=5, n=6, half=6):

ছোট array a-তে cut i, বড় array b-তে cut j = half - i

চেষ্টা i=3, j=3:
  a:  1  3  8 | 9  15
  b:  7 11 18 | 19 21 25
  বাঁ-max = max(a[2]=8,  b[2]=18) = 18
  ডান-min = min(a[3]=9,  b[3]=19) = 9
  18 <= 9? না -> বাঁ অংশে বড় element, a-র cut বাঁয়ে সরাও

চেষ্টা i=2, j=4:
  a:  1  3 | 8  9 15
  b:  7 11 18 19 | 21 25
  বাঁ-max = max(a[1]=3,  b[3]=19) = 19  ... এখনো বড়, সরাও
  ...
সঠিক cut-এ: a[i-1] <= b[j] এবং b[j-1] <= a[i] -> median এই 4 boundary থেকে

8. Example input and 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

9. Brute force thinking

প্রথম সরল চিন্তা: দুটো 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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

ছোট 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)।

13. Thinking tweak

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

14. Step-by-step dry run

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

15. Python solution

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!")

16. Line-by-line code explanation

• 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 যাচাই করতে।

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

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

22. Similar harder problems

• 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/

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "দুই 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।