005 — Merge Sorted Array¶

Source¶

Original source: Classic two-pointer merge exercise
Platform: LeetCode — https://leetcode.com/problems/merge-sorted-array/
Topic: array
Difficulty: Easy
Pattern: two pointers (পেছন থেকে সামনে)
Basic idea inherited from: pair-sum-এর pointer movement — দুই pointer, কিন্তু এবার merge-এর জন্য পেছন থেকে

1. Problem in simple words¶

দুটো sorted array nums1 আর nums2 দেওয়া। nums1-এর শুরুতে m-টা আসল value, তারপর n-টা খালি (0 দিয়ে রাখা) ঘর — মোট m+n লম্বা। nums2-তে n-টা value। দুটোকে merge করে একটা sorted array বানাও, পুরোটা nums1-এর ভেতরেই (in place)। আলাদা array ফেরত দিতে হবে না, nums1 নিজেই বদলে যাবে।

nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6],          n = 3
ফল (nums1) = [1, 2, 2, 3, 5, 6]

2. Which basic idea does this inherit from?¶

ভিত two-pointer movement (problem 1, 4-এর জ্ঞাতি)। কিন্তু চালাকিটা: সামনে থেকে merge করলে nums1-এর এখনো-না-পড়া value চাপা পড়ে যায়। তাই পেছন থেকে — সবচেয়ে বড় value আগে — বসালে যে ঘরগুলো ভরছি সেগুলো এমনিতেই খালি (0) থাকে। pair-sum-এর মতোই pointer-রা purpose নিয়ে সরে।

3. What is the hidden math or logic?¶

লুকানো logic: nums1-এর শেষ n ঘর খালি, আর merge করা array-র সবচেয়ে বড় element ঠিক সেখানেই (একদম শেষে) বসবে। দুই array-র শেষ থেকে বড়টা তুলে শেষ খালি ঘরে রাখি, তারপর এক ঘর পিছিয়ে আসি — invariant: nums1[k+1..] সবসময় সঠিকভাবে sorted-ভরা।

4. Which data structure is needed?¶

কোনো extra array লাগে না — শুধু তিনটা integer pointer: i (nums1-এর আসল অংশের শেষ), j (nums2-এর শেষ), k (nums1-এর একদম শেষ ঘর, যেখানে লিখব)। O(1) extra space।

5. Why this data structure fits¶

array index O(1) read/write দেয়, তাই শেষ ঘর থেকে সামনের দিকে সরাসরি লেখা যায়। nums1-এ already খালি জায়গা (trailing zeros) থাকায় নতুন buffer-এর দরকারই নেই — পেছন-থেকে লেখার ফলে কখনো না-পড়া value overwrite হয় না।

6. Real-life analogy¶

দুই গাদা তাস, দুটোই উপরে-বড় করে সাজানো। তুমি একটা বড় ফাঁকা জায়গায় শেষ থেকে সাজাতে চাও। দুই গাদার উপরের (সবচেয়ে বড়) তাস তুলনা করে বড়টা সবচেয়ে ডানের খালি জায়গায় রাখো, তারপর বাঁ দিকে এক ঘর সরে আবার করো — গাদা খালি হওয়া পর্যন্ত।

7. Visual explanation¶

nums1=[1,2,3,0,0,0] (m=3), nums2=[2,5,6] (n=3):

i->শেষ আসল nums1, j->শেষ nums2, k->শেষ ঘর

[1,2,3,_,_,_]  i=2(3) j=2(6) k=5: 6>3 -> nums1[5]=6  [1,2,3,_,_,6] j=1 k=4
               i=2(3) j=1(5) k=4: 5>3 -> nums1[4]=5  [1,2,3,_,5,6] j=0 k=3
               i=2(3) j=0(2) k=3: 3>2 -> nums1[3]=3  [1,2,3,3,5,6] i=1 k=2
               i=1(2) j=0(2) k=2: 2>2 মিথ্যা -> nums1[2]=2  [1,2,2,3,5,6] j=-1 k=1
               j<0 -> থামো

ফল: [1,2,2,3,5,6]

8. Example input and output¶

Input : nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3 -> [1,2,2,3,5,6]

Edge case 1 (nums2 খালি): nums1=[1], m=1, nums2=[], n=0 -> [1]
Edge case 2 (nums1 ফাঁকা): nums1=[0], m=0, nums2=[1], n=1 -> [1]

9. Brute force thinking¶

প্রথম সরল চিন্তা: nums2-এর value গুলো nums1-এর খালি ঘরে বসাও, তারপর পুরো nums1 sort করো।

nums1[m:] = nums2
nums1.sort()

10. Why brute force is slow¶

পুরো array sort করা O((m+n) log(m+n)) — অথচ দুটো অংশ already sorted, তাই merge মাত্র O(m+n)-এ হওয়া উচিত। sort সেই sorted-property-টা কাজে লাগায় না, তাই বাড়তি log factor গুনতে হয়।

11. Key observation¶

মূল observation: nums1-এর খালি জায়গা পেছনে, আর merge-এর বড় element-ও পেছনে বসে। দুটো মিলে যায় — তাই পেছন থেকে লিখলে কখনো এমন ঘরে লিখব না যেখানে এখনো-না-পড়া আসল value আছে।

12. Optimized intuition¶

তিন pointer: i=m-1, j=n-1, k=m+n-1। যতক্ষণ nums2-তে কিছু বাকি (j>=0): nums1[i] আর nums2[j]-এর বড়টা nums1[k]-এ রাখো, সেই pointer আর k এক ঘর পিছাও। j<0 হলে থামো — বাকি nums1 value already জায়গামতো।

13. Thinking tweak¶

মোচড়: "ছোট element আগে, সামনে থেকে merge" (যা overwrite করে) ভুলে গিয়ে ভাবো "বড় element আগে, পেছন থেকে বসাই।" খালি জায়গা যেহেতু পেছনে, এই দিক উল্টানোই extra buffer-এর দরকার মিটিয়ে দেয়।

14. Step-by-step dry run¶

Input nums1=[1,2,3,0,0,0] (m=3), nums2=[2,5,6] (n=3):

i=2, j=2, k=5: nums2[2]=6 > nums1[2]=3 → nums1[5]=6; j=1, k=4।
i=2, j=1, k=4: 5 > 3 → nums1[4]=5; j=0, k=3।
i=2, j=0, k=3: nums1[2]=3 > nums2[0]=2 → nums1[3]=3; i=1, k=2।
i=1, j=0, k=2: nums1[1]=2 > nums2[0]=2 মিথ্যা → nums1[2]=2; j=-1, k=1।
j<0 → থামো। ফল [1,2,2,3,5,6]।

15. Python solution¶

def merge(nums1, m, nums2, n):
    i = m - 1                # nums1-এর আসল অংশের শেষ
    j = n - 1                # nums2-এর শেষ
    k = m + n - 1            # লেখার জায়গা (একদম শেষ)
    while j >= 0:            # nums2 শেষ হলেই কাজ শেষ
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    return nums1

# ---- tests ----
a = [1, 2, 3, 0, 0, 0]
merge(a, 3, [2, 5, 6], 3)
assert a == [1, 2, 2, 3, 5, 6]

b = [1]
merge(b, 1, [], 0)
assert b == [1]            # nums2 খালি

c = [0]
merge(c, 0, [1], 1)
assert c == [1]            # nums1-এ আসল কিছু নেই
print("সব test pass!")

16. Line-by-line code explanation¶

i, j, k — তিন pointer যথাক্রমে nums1-এর আসল শেষ, nums2-এর শেষ, লেখার শেষ ঘর।
while j >= 0 — nums2-এর সব value বসানো হলেই থামি (nums1-এর বাকি value নিজের জায়গাতেই আছে)।
if i >= 0 and nums1[i] > nums2[j] — nums1-এ এখনো value আছে এবং সেটা বড় হলে সেটাই পেছনে বসাই।
else: nums1[k] = nums2[j] — নাহলে nums2-এর value বসাই (i ফুরিয়ে গেলেও এই শাখা চলে)।
k -= 1 — প্রতি লেখার পর লেখার জায়গা এক ঘর বাঁয়ে।

17. Output walkthrough¶

[1,2,3,0,0,0]+[2,5,6]: পেছন থেকে 6,5,3,2 বসতে বসতে [1,2,2,3,5,6] — assert pass। nums2 খালি হলে loop চলেই না, nums1 অপরিবর্তিত [1]। nums1-এ আসল কিছু না থাকলে nums2-র 1 বসে [1]। শেষে print: সব test pass!।

18. Time complexity¶

O(m + n) — প্রতিটা element ঠিক একবার করে বসে; pointer গুলো একবারই পুরো পথ পেরোয়।

19. Space complexity¶

O(1) — শুধু তিনটা pointer; merge পুরোটা nums1-এর ভেতরেই।

20. Common mistakes¶

সামনে থেকে merge করা — তখন nums1-এর না-পড়া value overwrite হয়ে যায় (এজন্যই পেছন থেকে)।
if i >= 0 শর্ত বাদ দেওয়া — i -1 হয়ে গেলে nums1[-1] ভুল (Python-এ wrap করে) value পড়ে।
nums2 শেষ হওয়ার শর্তের বদলে i শেষ হওয়া দেখা — nums2-এর বাকি value তখন বসানো হয় না।

21. Which basic problem this inherits from¶

ভিত্তি: two-pointer traversal (problem 1, 4) আর merge sort-এর merge step। এই পেছন-থেকে-লেখার কৌশল trapping rain water (#21)-এর দুই-প্রান্ত pointer চিন্তারও আত্মীয়। chapter-এর ../patterns.md-এর "Pattern 1 — Two Pointers" দেখো।

22. Similar harder problems¶

Merge k Sorted Lists (heap লাগে) — https://leetcode.com/problems/merge-k-sorted-lists/
Sort Colors (Dutch national flag, three pointers) — https://leetcode.com/problems/sort-colors/
Squares of a Sorted Array (দুই প্রান্ত merge) — https://leetcode.com/problems/squares-of-a-sorted-array/

23. Pattern learned¶

Two pointers from the back (in-place merge): খালি জায়গা যেদিকে, সেদিক থেকে বড় element আগে বসিয়ে overwrite এড়ানো — extra buffer ছাড়াই merge।

24. Final summary¶

ভবিষ্যতের আমাকে: "in place merge = পেছন থেকে, বড় element আগে।" দুটো sorted জিনিস একটার ভেতরে merge করতে হলে trailing খালি জায়গা থেকে উল্টো হাঁটার কথা মনে করবে।

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