Problem link ও উৎস
- **Original source:** Classic in-place index-marking exercise
- **Platform:** LeetCode —
- **Topic:** array / in-place hashing
- **Difficulty:** Hard
- **Pattern:** in-place index marking (cyclic placement)
- **Basic idea inherited from:** array-কেই নিজের hash map বানানোর trick — মান `v`-কে index `v-1`-এ বসানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array `nums` দেওয়া (ধনাত্মক, ঋণাত্মক, শূন্য — যেকোনো কিছু থাকতে পারে)। সবচেয়ে ছোট যে **ধনাত্মক পূর্ণসংখ্যা** (1, 2, 3, ...) array-তে নেই, সেটা বের করো। শর্ত: **O(n) সময়** এবং **O(1) extra space** — অর্থাৎ আলাদা set/array বানানো যাবে না।
```text
nums = [3, 4, -1, 1]
আছে: 1, 3, 4 ; নেই: 2 -> উত্তর 2
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1, 2, 0] -> 3
Input : [3, 4, -1, 1] -> 2
Input : [7, 8, 9, 11, 12]-> 1 (1-ই নেই)
Edge case 1 (সব আছে): [1] -> 2 (উত্তর n+1)
Edge case 2 (খালি): [] -> 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো ক্লোকরুমে 1 থেকে n নম্বরের হুক, আর প্রতিটা কোটে একটা টোকেন-নম্বর লেখা। নিয়ম: টোকেন `k`-ওয়ালা কোট হুক `k`-তেই ঝুলবে। সবাইকে নিজ নিজ হুকে সাজিয়ে দাও (যাদের নম্বর 1..n)। শেষে হুকগুলো বাঁ থেকে দেখো — প্রথম যে হুকে ভুল/অনুপস্থিত কোট, সেই হুক-নম্বরই হারানো প্রথম টোকেন।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত একটা চালাকি: **array-কেই নিজের hash map বানাও**। আলাদা hash set হলে membership O(1)-এ দেখা যেত, কিন্তু সেটা O(n) extra space। বদলে আমরা মানটাকে তার "ঘরে" রাখি — মান `v` (যদি `1..n`-এর মধ্যে) বসে index `v-1`-এ। তাহলে index নিজেই বলে দেয় কোন সংখ্যা উপস্থিত। এটা hashing-এর সবচেয়ে minimal রূপ; গভীরে: [../../05-hashing/](../../05-hashing/README.md)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic **pigeonhole principle**: `n`-দৈর্ঘ্যের array-তে সবচেয়ে ছোট অনুপস্থিত ধনাত্মক সংখ্যা সবসময় `1` থেকে `n+1`-এর মধ্যেই থাকবে। কেন? কারণ `n`টা ঘরে বড়জোর `1..n` সবগুলো ধরা সম্ভব; সব ধরলে উত্তর `n+1`, নইলে `1..n`-এর কোনোটা বাদ পড়েছে। তাই `n`-এর বাইরের বা অধনাত্মক মান অগ্রাহ্য করা যায় — শুধু `1..n` রাখার চেষ্টা করি।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো **নতুন** structure নয় — input array `nums` নিজেই data structure। প্রতিটা মান `v ∈ [1, n]`-কে তার সঠিক ঘরে (`index v-1`) swap করে বসাই (cyclic sort)। সাথে শুধু কয়েকটা integer। মোট O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্নটা আসলে "কোন সংখ্যা উপস্থিত?" — যা একটা membership query, hash-এর কাজ। কিন্তু value-গুলো ছোট পরিসরে (`1..n`) সীমাবদ্ধ বলে আমরা value-কেই index বানিয়ে array-টাকে perfect hash table হিসেবে ব্যবহার করতে পারি: ঘর `i`-তে যদি `i+1` থাকে, তবে `i+1` উপস্থিত। array mutable বলে in-place এই বিন্যাস সম্ভব, extra memory ছাড়াই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সব সংখ্যা একটা hash set-এ ভরো, তারপর 1, 2, 3, ... করে গুনতে গুনতে যেটা set-এ নেই সেটাই উত্তর।
```text
seen = set(nums)
i = 1
while i in seen:
i += 1
return i
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা O(n) **time**-এ ঠিক উত্তর দেয়, কিন্তু hash set-টা **O(n) extra space** নেয় — অথচ problem কড়াভাবে O(1) extra চায়। চালাকিটা হলো: আলাদা set-এর বদলে input array-র index-কেই "এই সংখ্যা আছে কিনা"-র চিহ্ন হিসেবে ব্যবহার করা, তাই বাড়তি memory লাগে না।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
দুটো observation: (১) উত্তর সবসময় `1..n+1`-এর মধ্যে (pigeonhole), তাই `1..n`-এর বাইরের মান অপ্রাসঙ্গিক। (২) মান `v ∈ [1,n]`-কে index `v-1`-এ বসিয়ে দিলে, পরে শুধু বাঁ-থেকে scan করে প্রথম যে index `i`-তে `nums[i] != i+1`, সেই `i+1`-ই হারানো সংখ্যা — index নিজেই membership বলে দেয়।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
দুই pass:
- **Pass 1 (placement):** প্রতিটা `i`-তে যতক্ষণ `nums[i]` মান `1..n`-এর মধ্যে এবং নিজের সঠিক ঘরে (`nums[nums[i]-1] != nums[i]`) নেই, ততক্ষণ swap করে তাকে `index nums[i]-1`-এ পাঠাও (cyclic)। ডুপ্লিকেট/range-বাইরের মান এমনিতেই এড়ানো হয়।
- **Pass 2 (scan):** বাঁ থেকে দেখো প্রথম কোন index `i`-তে `nums[i] != i+1` — উত্তর `i+1`। সব মিললে উত্তর `n+1`।
মোট O(n): প্রতিটা swap অন্তত একটা সংখ্যাকে তার চিরস্থায়ী ঘরে বসায়, তাই মোট swap ≤ n।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "membership জানতে আলাদা set লাগবেই" ধারণা ছাড়ো। ভাবো "মানটাকে তার নিজের ঘরে (`v` → index `v-1`) বসিয়ে দিই — তখন array-র index-ই hash key, আর ঘরে কী আছে সেটাই value-র উপস্থিতি বলে দেয়।" এতে hash table আর input array এক হয়ে যায়, extra space 0।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [3, 4, -1, 1]` (n=4) — প্রতিটা মান `v`-কে index `v-1`-এ swap:
```text
শুরু: [ 3, 4, -1, 1]
i=0: 3 -> idx2 (swap): [-1, 4, 3, 1] (idx0=-1, range বাইরে, থামো)
i=1: 4 -> idx3 (swap): [-1, 1, 3, 4] 1 -> idx0 (swap): [ 1, -1, 3, 4] থামো
i=2: 3 ঠিক জায়গায় (idx2); i=3: 4 ঠিক জায়গায় (idx3)
সাজানো: [ 1, -1, 3, 4]
scan: idx0=1 ✓, idx1=-1 ✗ -> অনুপস্থিত 2
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[1, 2, 0]` (n=3):
1. `i=0`: `nums[0]=1`, range-এ, `nums[0]==1` ঠিক জায়গায় → থামো।
2. `i=1`: `nums[1]=2`, `nums[1]==2` ঠিক জায়গায় → থামো।
3. `i=2`: `nums[2]=0`, range-এর বাইরে (`1..3` নয়) → থামো। array `[1,2,0]`।
4. scan: idx0=1✓, idx1=2✓, idx2=0 ≠ 3 → উত্তর `3`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def first_missing_positive(nums):
n = len(nums)
for i in range(n):
# nums[i] কে তার সঠিক ঘরে (index nums[i]-1) পাঠাও
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
correct = nums[i] - 1
nums[i], nums[correct] = nums[correct], nums[i]
for i in range(n):
if nums[i] != i + 1: # প্রথম বেমানান ঘর
return i + 1
return n + 1 # 1..n সব আছে -> উত্তর n+1
# ---- tests ----
assert first_missing_positive([1, 2, 0]) == 3
assert first_missing_positive([3, 4, -1, 1]) == 2
assert first_missing_positive([7, 8, 9, 11, 12]) == 1
assert first_missing_positive([1]) == 2 # সব আছে -> n+1
assert first_missing_positive([]) == 1 # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `n = len(nums)` — পরিসর `1..n`; এর বাইরের কিছু লাগবে না।
- `while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]:` — মান range-এ আছে **এবং** এখনো নিজের ঘরে নেই, তবেই swap; দ্বিতীয় শর্ত duplicate-এ অসীম loop ঠেকায়।
- `correct = nums[i] - 1` — মান `v`-এর প্রাপ্য index `v-1`।
- `nums[i], nums[correct] = nums[correct], nums[i]` — swap করে মানটাকে তার ঘরে পাঠাই; নতুন আসা মান নিয়ে `while` আবার পরীক্ষা করে।
- দ্বিতীয় loop — প্রথম যে index-এ `nums[i] != i+1`, সেই `i+1` অনুপস্থিত।
- `return n + 1` — `1..n` সব সাজানো থাকলে সবচেয়ে ছোট অনুপস্থিত `n+1`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,2,0]` → placement-এর পর `[1,2,0]`, idx2 বেমানান → `3`, assert pass। `[3,4,-1,1]` → সাজানোর পর `[1,-1,3,4]`, idx1 বেমানান → `2`; `[7,8,9,11,12]` → সব range-বাইরে, কিছুই বসে না, idx0 ≠ 1 → `1`; `[1]` → সব ঠিক, `n+1=2`; `[]` → `0+1=1`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — বাইরের loop n বার; ভেতরের `while`-এর প্রতিটা সফল swap একটা সংখ্যাকে তার চিরস্থায়ী ঘরে বসায়, তাই সব মিলিয়ে swap সংখ্যা ≤ n। দ্বিতীয় scan O(n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু কয়েকটা integer; input array-র ভেতরেই সব কাজ, কোনো extra set/array নেই।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `while`-এর duplicate-গার্ড (`nums[nums[i]-1] != nums[i]`) বাদ দেওয়া — একই মান দুবার থাকলে অসীম swap-loop।
- swap-এ ভুল ক্রমে assignment (Python tuple-swap ঠিক, কিন্তু temp দিয়ে করলে আগে `nums[i]` বদলে ফেললে `correct`-এর হিসাব নষ্ট)।
- range-শর্ত (`1 <= nums[i] <= n`) ভুলে negative/বড় মান নিয়েও swap করতে যাওয়া — index error বা ভুল।
- `i+1`-এর বদলে `i` ফেরত দেওয়া — index 0-based, কিন্তু সংখ্যা 1-based।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: "array-কেই hash map বানানো" (value→index placement), যা cyclic-sort ঘরানার core। membership-by-index idea-র জন্য [../../05-hashing/](../../05-hashing/README.md) দেখো; আর pigeonhole-এর গণিত [../../01-math-based-programming-fundamentals/03-counting-combinatorics/](../../01-math-based-programming-fundamentals/03-counting-combinatorics/README.md)-এ। chapter-এর [../patterns.md](../patterns.md)-এ এটা index-marking-এর hard প্রতিনিধি।
### পরের অনুশীলন {#22-similar-harder-problems}
- Find All Numbers Disappeared in an Array (একই index-marking) —