Problem link ও উৎস
- **Original source:** Classic two-pointer (slow/fast) exercise
- **Platform:** LeetCode —
- **Topic:** array
- **Difficulty:** Easy
- **Pattern:** two pointers (slow/fast, same direction)
- **Basic idea inherited from:** two-pointer reversal-এর idea — দুটো index, কিন্তু এবার একই দিকে
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা **sorted** (বাড়ন্ত order-এ সাজানো) integer array `nums` দেওয়া। প্রতিটা আলাদা value যেন শুধু **একবার** থাকে — duplicate গুলো in place সরিয়ে দাও। কতগুলো unique value আছে (`k`) সেটা ফেরত দাও, আর `nums`-এর প্রথম `k` ঘরে সেই unique value গুলো order ঠিক রেখে বসিয়ে দাও। `k`-এর পরে কী আছে তা matter করে না।
```text
nums = [1, 1, 2] -> k = 2, nums প্রথম 2 ঘর = [1, 2]
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1, 1, 2] -> k = 2, nums[:2] = [1, 2]
Input : [0,0,1,1,1,2,2,3,3,4] -> k = 5, nums[:5] = [0,1,2,3,4]
Edge case (খালি): [] -> k = 0
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একসারি অতিথি লাইন ধরে আসছে, name অনুযায়ী আগে থেকে সাজানো। তুমি একটা guest book-এ প্রতিটা নাম একবারই লিখতে চাও। নতুন কেউ এলে তার নাম তোমার লেখা শেষ নামের সাথে মেলাও — আলাদা হলেই কেবল নতুন লাইনে লেখো; একই হলে এড়িয়ে যাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত problem 1-এর **two-pointer** idea — তবে সেখানে দুই pointer দুই প্রান্ত থেকে আসত, এখানে দুটোই **একই দিকে** চলে: একটা `slow` (কোথায় পরের unique বসবে) আর একটা `fast` (array scan করছে)। same-direction slow/fast হলো array compaction-এর মূল কঙ্কাল।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা invariant: **`nums[0..slow]` সবসময় এ পর্যন্ত পাওয়া unique value গুলো, order ঠিক রেখে।** array sorted বলে সব duplicate পাশাপাশি — তাই নতুন value চেনা সহজ: `nums[fast]` যদি `nums[slow]`-এর সমান না হয়, তবেই সেটা নতুন।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না — array টা আছে, আর শুধু **দুটো integer pointer** (`slow`, `fast`)। O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
array index দিয়ে O(1) read/write দেয়, তাই `nums[fast]`-কে সরাসরি `nums[slow+1]`-এ লিখে দেওয়া যায় কোনো shifting ছাড়াই। sorted property থাকায় duplicate detect করতে শুধু পাশের ঘরের সাথে তুলনা — set/dict-এর দরকারই নেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: একটা `set`-এ unique গুলো রাখো, তারপর sort করে আবার `nums`-এ ফেরত লিখি।
```text
unique = sorted(set(nums))
nums[:len(unique)] = unique
return len(unique)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
`set` বানালে **O(n) extra space**, আর sorted set আবার **O(n log n)** — অথচ array already sorted, sort একদম বাড়তি কাজ। problem চায় O(1) extra space, in place; পাশের ঘরের তুলনাই যথেষ্ট, পুরো set বানানোর দরকার নেই।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: array **sorted** বলে কোনো value-র সব copy টানা পাশাপাশি বসে আছে। তাই duplicate চিনতে দূরের কিছু মনে রাখার দরকার নেই — শুধু "এইটা কি ঠিক-আগে লেখা unique-এর সমান?" এটুকুই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`slow` শুরুতে 0 (প্রথম element তো নিশ্চিত unique)। `fast` 1 থেকে শেষ পর্যন্ত হাঁটে। প্রতিবার `nums[fast] != nums[slow]` হলে নতুন value পেলাম → `slow` এক বাড়িয়ে সেখানে `nums[fast]` লিখি। শেষে unique সংখ্যা `slow + 1`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "duplicate মুছব" (যা shifting চায়) ভাবার বদলে ভাবো "unique গুলো সামনে নতুন করে লিখব।" তখন delete-এর O(n) shift গায়েব; একটা write-pointer দিয়ে এক pass-এই হয়ে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [0, 0, 1, 1, 2]`:
```text
slow নির্দেশ করে শেষ unique-এর জায়গা; fast scan করে।
start: slow=0 [ (0) 0 1 1 2 ] fast=1
f=1: nums[1]=0 == nums[slow]=0 -> skip
f=2: nums[2]=1 != 0 -> slow=1; nums[1]=1 [0,(1),1,1,2]
f=3: nums[3]=1 == nums[slow]=1 -> skip
f=4: nums[4]=2 != 1 -> slow=2; nums[2]=2 [0,1,(2),1,2]
k = slow+1 = 3 ; প্রথম 3 ঘর = [0,1,2]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[1, 1, 2]`:
1. শুরু: `slow=0` (`nums[0]=1` ধরে নিলাম unique)।
2. `fast=1`: `nums[1]=1 == nums[slow]=1` → duplicate, skip।
3. `fast=2`: `nums[2]=2 != nums[slow]=1` → `slow=1`; `nums[1]=2`। array এখন `[1,2,2]`।
4. loop শেষ। `k = slow + 1 = 2`; প্রথম 2 ঘর `[1, 2]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def remove_duplicates(nums):
if not nums: # খালি array
return 0
slow = 0 # শেষ unique-এর index
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]: # নতুন value পেলাম
slow += 1
nums[slow] = nums[fast] # সামনে লিখে দাও
return slow + 1 # unique-এর সংখ্যা
# ---- tests ----
nums = [1, 1, 2]
k = remove_duplicates(nums)
assert k == 2 and nums[:k] == [1, 2]
nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k2 = remove_duplicates(nums2)
assert k2 == 5 and nums2[:k2] == [0, 1, 2, 3, 4]
assert remove_duplicates([]) == 0 # খালি array
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if not nums: return 0` — খালি array হলে unique 0।
- `slow = 0` — প্রথম element আপনাআপনি unique, তাই write-pointer 0-তে।
- `for fast in range(1, len(nums))` — দ্বিতীয় element থেকে scan।
- `if nums[fast] != nums[slow]` — sorted বলে পাশের সাথে আলাদা মানেই নতুন।
- `slow += 1; nums[slow] = nums[fast]` — নতুন unique-কে সামনের ঘরে বসাই।
- `return slow + 1` — index `slow` পর্যন্ত ভরা, তাই গুনতি `slow + 1`।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1,1,2]`: fast=1 duplicate skip, fast=2 নতুন → `nums=[1,2,2]`, `slow=1`, `k=2`, `nums[:2]=[1,2]` — assert pass। বড় array দেয় `k=5`, `[0,1,2,3,4]`। খালি দেয় 0। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — `fast` array-র উপর ঠিক একবার হাঁটে; প্রতিটা step O(1)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু দুটো pointer; array-র ভেতরেই overwrite হয়।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- খালি array আলাদা না ধরা — `slow=0` ধরে `slow+1=1` ভুল ফেরত দিত।
- `nums[fast]`-কে আগের লেখা unique (`nums[slow]`)-এর বদলে দূরের কিছুর সাথে তুলনা করা — sorted বলে পাশের তুলনাই যথেষ্ট।
- `slow` বাড়ানো আর লেখার order উল্টে ফেলা — তখন value চাপা পড়ে যায়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: problem 1-এর two-pointer, এখন same-direction slow/fast রূপে। এই একই কঙ্কাল move zeroes (#6)-এও — শুধু "নতুন কিনা" শর্তের জায়গায় "zero নয় কিনা"। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 1 — Two Pointers" দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Remove Duplicates from Sorted Array II (প্রতিটা value বড়জোর 2 বার) —