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:** remove-duplicates-এর skeleton — slow write-pointer + fast read-pointer
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা integer array `nums` দেওয়া। সব `0` কে array-র **শেষে** পাঠাও, আর non-zero গুলোর **relative order ঠিক রেখে**। কাজটা in place — নতুন array না বানিয়ে।
```text
nums = [0, 1, 0, 3, 12] -> [1, 3, 12, 0, 0]
(1, 3, 12 আগের order-এই; zero গুলো শেষে)
```
### Input ও output {#8-example-input-and-output}
```text
Input : [0, 1, 0, 3, 12] -> [1, 3, 12, 0, 0]
Edge case 1 (সব zero): [0, 0, 0] -> [0, 0, 0]
Edge case 2 (zero নেই): [1, 2, 3] -> [1, 2, 3]
Edge case 3 (একটা): [0] -> [0]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একটা ট্রে-তে কিছু পূর্ণ গ্লাস আর কিছু খালি গ্লাস এলোমেলো। তুমি চাও পূর্ণ গ্লাসগুলো (একই order-এ) সামনে চলে আসুক, খালিগুলো পেছনে জমুক। বাঁ থেকে হাঁটতে হাঁটতে পূর্ণ গ্লাস পেলেই সামনের পরের ফাঁকা জায়গায় এনে রাখো; খালি গ্লাস পেলে এড়িয়ে যাও।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
হুবহু problem 4 (remove duplicates)-এর **slow/fast skeleton**। সেখানে শর্ত ছিল "নতুন value কিনা"; এখানে শর্ত "non-zero কিনা"। `slow` বলে পরের non-zero কোথায় বসবে, `fast` পুরো array scan করে। একই কঙ্কাল, শুধু শর্ত বদল।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা invariant: **`nums[0..slow-1]` সবসময় এ পর্যন্ত পাওয়া সব non-zero, order ঠিক রেখে।** `fast` যখন non-zero পায়, সেটাকে `slow`-এ এনে `slow` এক বাড়াই। শেষে `slow` থেকে array-র শেষ পর্যন্ত সব আপনাআপনি zero (swap version-এ zero গুলো পিছনে চলে যায়)।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra structure লাগে না — array আছে, আর **দুটো integer pointer** (`slow`, `fast`)। O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
array O(1) index access/swap দেয়, তাই non-zero element-কে সরাসরি সামনের সঠিক ঘরে swap করা যায়। order রক্ষা পায় কারণ আমরা বাঁ-থেকে-ডান একই ক্রমে non-zero গুলো বসাই — কোনো structure-এ আলাদা করে জমা রাখার দরকার নেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: সব non-zero নতুন list-এ তুলে নাও, পেছনে যত zero দরকার ততগুলো জুড়ে দাও, তারপর `nums`-এ copy করো।
```text
out = [x for x in nums if x != 0]
out += [0] * (len(nums) - len(out))
nums[:] = out
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ঠিক কাজ করে কিন্তু **O(n) extra space** নেয় (নতুন list)। problem in place, O(1) space চায়। আলাদা list-এর দরকার নেই — একটা write-pointer দিয়ে array-র ভেতরেই non-zero সামনে আনা যায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: zero "সরানোর" দরকার নেই; শুধু **non-zero গুলো order ঠিক রেখে সামনে packing** করলেই zero গুলো এমনিতেই পেছনে চলে যায়। (swap করলে zero নিজে থেকে slow-এর ঘরে গিয়ে বসে।)
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`slow=0`। `fast` পুরো array-তে হাঁটে। `nums[fast]` non-zero হলে `nums[slow]`-এর সাথে swap করো আর `slow` এক বাড়াও। zero হলে কিছু না করে এগিয়ে যাও। শেষে non-zero গুলো সামনে (order সহ), zero গুলো পেছনে।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "zero গুলো শেষে ঠেলব" ভাবার বদলে ভাবো "non-zero গুলো সামনে টানব।" তখন remove-duplicates-এর সেই একই slow/fast packing কাজে লেগে যায় — শুধু শর্ত `!= 0`।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [0, 1, 0, 3, 12]` (swap version, slow = পরের non-zero যেখানে বসবে):
```text
slow=0
f=0: nums[0]=0 -> skip
f=1: nums[1]=1 -> swap(0,1) [1,0,0,3,12] slow=1
f=2: nums[2]=0 -> skip
f=3: nums[3]=3 -> swap(1,3) [1,3,0,0,12] slow=2
f=4: nums[4]=12 -> swap(2,4) [1,3,12,0,0] slow=3
ফল: [1,3,12,0,0]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[0, 1, 0, 3, 12]`:
1. `slow=0`। `fast=0`: `nums[0]=0` → skip।
2. `fast=1`: `nums[1]=1` non-zero → swap `nums[0],nums[1]` → `[1,0,0,3,12]`; `slow=1`।
3. `fast=2`: `nums[2]=0` → skip।
4. `fast=3`: `nums[3]=3` non-zero → swap `nums[1],nums[3]` → `[1,3,0,0,12]`; `slow=2`।
5. `fast=4`: `nums[4]=12` non-zero → swap `nums[2],nums[4]` → `[1,3,12,0,0]`; `slow=3`। ফল `[1,3,12,0,0]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def move_zeroes(nums):
slow = 0 # পরের non-zero যেখানে বসবে
for fast in range(len(nums)):
if nums[fast] != 0: # non-zero পেলাম
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
return nums
# ---- tests ----
a = [0, 1, 0, 3, 12]
move_zeroes(a)
assert a == [1, 3, 12, 0, 0]
b = [0, 0, 0]
move_zeroes(b)
assert b == [0, 0, 0] # সব zero
c = [1, 2, 3]
move_zeroes(c)
assert c == [1, 2, 3] # zero নেই
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `slow = 0` — পরের non-zero কোন ঘরে বসবে তার write-pointer।
- `for fast in range(len(nums))` — পুরো array একবার scan।
- `if nums[fast] != 0` — শুধু non-zero হলেই কাজ।
- `nums[slow], nums[fast] = nums[fast], nums[slow]` — non-zero-কে সামনে আনি; zero (থাকলে) পেছনে চলে যায়।
- `slow += 1` — পরের non-zero-র জন্য জায়গা এক ঘর এগোলো।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[0,1,0,3,12]`: 1, 3, 12 ক্রমে সামনে swap হয়ে `[1,3,12,0,0]` — assert pass। সব-zero array swap-এ অপরিবর্তিত; zero-নেই array-তে প্রতিটা element নিজের সাথে swap হয়ে অপরিবর্তিত। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
slow/fast same-direction two pointers — non-zero পেলে `slow`-এ swap করে `slow` এগোই; zero এড়িয়ে যাই।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function moveZeroes(nums) {
let slow = 0; // পরের non-zero যেখানে বসবে
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== 0) {
[nums[slow], nums[fast]] = [nums[fast], nums[slow]]; // non-zero সামনে
slow++;
}
}
return nums;
}
// ---- test cases (file-এর example + edge case) ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(moveZeroes([0, 1, 0, 3, 12]), [1, 3, 12, 0, 0]), "basic");
assert(eq(moveZeroes([0, 0, 0]), [0, 0, 0]), "সব zero");
assert(eq(moveZeroes([1, 2, 3]), [1, 2, 3]), "zero নেই");
assert(eq(moveZeroes([0]), [0]), "একটা");
assert(eq(moveZeroes([1, 0, 2, 0, 3]), [1, 2, 3, 0, 0]), "mixed, order রক্ষা");
console.log("সব JS test pass!");
```
> **JS টীকা:** swap `[a, b] = [b, a]` (destructuring) — temp লাগে না, in-place থাকে, তাই O(1) extra space। zero-element-এ `slow` বাড়িও না (তখন zero "valid" ধরা পড়ে packing ভাঙবে)। non-zero গুলো বাঁ-থেকে-ডান একই ক্রমে বসে বলে relative order অটুট।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function moveZeroes(nums: number[]): number[] {
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== 0) {
[nums[slow], nums[fast]] = [nums[fast], nums[slow]];
slow++;
}
}
return nums;
}
function expectArr(actual: number[], expected: number[], msg = ""): void {
if (JSON.stringify(actual) !== JSON.stringify(expected)) {
throw new Error(`FAIL ${msg}: [${actual}]`);
}
}
expectArr(moveZeroes([0, 1, 0, 3, 12]), [1, 3, 12, 0, 0], "basic");
expectArr(moveZeroes([0, 0, 0]), [0, 0, 0], "all zero");
expectArr(moveZeroes([1, 2, 3]), [1, 2, 3], "no zero");
console.log("সব TS test pass!");
```
> **TS টীকা:** `nums: number[]` declare করায় in-place mutation-এর target স্পষ্ট; ভুলে readonly tuple বা অন্য টাইপ পাঠালে compile-time-এ ধরা পড়ে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — `fast` array-তে একবার হাঁটে; প্রতিটা step O(1)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু দুটো pointer; swap array-র ভেতরেই।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- order ভেঙে ফেলা — non-zero গুলো sort/অদলবদল করা; problem relative order রাখতে বলে।
- শুধু non-zero সামনে লিখে বাকি ঘর zero করতে ভুলে যাওয়া (write-only version-এ) — swap version-এ এই সমস্যা নেই।
- zero-element-এও `slow` বাড়িয়ে দেওয়া — তখন zero-ও "valid" ধরা পড়ে, packing ভুল হয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: problem 4 (remove duplicates)-এর slow/fast packing; শর্ত বদলে "non-zero কিনা"। দুটোই Pattern 1-এর same-direction two pointers-এর রূপ। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 1 — Two Pointers" দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Remove Element —