Problem link ও উৎস
- **Original source:** Classic two-pointer merge exercise
- **Platform:** LeetCode —
- **Topic:** array
- **Difficulty:** Easy
- **Pattern:** two pointers (পেছন থেকে সামনে)
- **Basic idea inherited from:** pair-sum-এর pointer movement — দুই pointer, কিন্তু এবার merge-এর জন্য পেছন থেকে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#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` নিজেই বদলে যাবে।
```text
nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6], n = 3
ফল (nums1) = [1, 2, 2, 3, 5, 6]
```
### Input ও output {#8-example-input-and-output}
```text
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]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
দুই গাদা তাস, দুটোই উপরে-বড় করে সাজানো। তুমি একটা বড় ফাঁকা জায়গায় শেষ থেকে সাজাতে চাও। দুই গাদার উপরের (সবচেয়ে বড়) তাস তুলনা করে বড়টা সবচেয়ে ডানের খালি জায়গায় রাখো, তারপর বাঁ দিকে এক ঘর সরে আবার করো — গাদা খালি হওয়া পর্যন্ত।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#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 হয় না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: `nums2`-এর value গুলো `nums1`-এর খালি ঘরে বসাও, তারপর পুরো `nums1` sort করো।
```text
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-এর দরকার মিটিয়ে দেয়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums1=[1,2,3,0,0,0] (m=3)`, `nums2=[2,5,6] (n=3)`:
```text
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]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `nums1=[1,2,3,0,0,0] (m=3)`, `nums2=[2,5,6] (n=3)`:
1. `i=2, j=2, k=5`: `nums2[2]=6 > nums1[2]=3` → `nums1[5]=6`; `j=1, k=4`।
2. `i=2, j=1, k=4`: `5 > 3` → `nums1[4]=5`; `j=0, k=3`।
3. `i=2, j=0, k=3`: `nums1[2]=3 > nums2[0]=2` → `nums1[3]=3`; `i=1, k=2`।
4. `i=1, j=0, k=2`: `nums1[1]=2 > nums2[0]=2` মিথ্যা → `nums1[2]=2`; `j=-1, k=1`।
5. `j<0` → থামো। ফল `[1,2,2,3,5,6]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
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` — প্রতি লেখার পর লেখার জায়গা এক ঘর বাঁয়ে।
### Output মিলিয়ে দেখা {#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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#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 তখন বসানো হয় না।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#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](../patterns.md)-এর "Pattern 1 — Two Pointers" দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Merge k Sorted Lists (heap লাগে) —