Problem link ও উৎস
- **Original source:** Classic two-pointer exercise
- **Platform:** LeetCode —
- **Topic:** array / string
- **Difficulty:** Easy
- **Pattern:** two pointers (দুই প্রান্ত থেকে swap)
- **Basic idea inherited from:** basic swap + index walk — দুটো index একসাথে হাঁটিয়ে value অদলবদল
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা character-এর array `s` দেওয়া আছে (যেমন `["h","e","l","l","o"]`)। তোমার কাজ: পুরো array টা **in place** উল্টে দাও — মানে নতুন কোনো array না বানিয়ে, একই array-র ভেতরেই প্রথম আর শেষ অদলবদল করতে করতে। কাজ শেষে `s` হয়ে যাবে `["o","l","l","e","h"]`।
```text
আগে : [h, e, l, l, o]
পরে : [o, l, l, e, h]
```
### Input ও output {#8-example-input-and-output}
```text
Input : ["h","e","l","l","o"] -> Output: ["o","l","l","e","h"]
Input : ["H","a","n","n","a","h"] -> Output: ["h","a","n","n","a","H"]
Edge case 1 (একটা element): ["a"] -> ["a"]
Edge case 2 (খালি array): [] -> []
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একসারি বইয়ের তাক ভাবো। তুমি চাও বইগুলোর order উল্টে যাক। সবচেয়ে বাঁয়ের বই আর সবচেয়ে ডানের বই হাতে নিয়ে জায়গা বদলে দাও, তারপর এক ঘর ভেতরে এসো — আবার বদলাও। মাঝে যখন দুই হাত মিলে যায়, কাজ শেষ। কোনো নতুন তাক লাগেনি।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **swap + দুই index একসাথে হাঁটানো**। তুমি যদি জানো কীভাবে দুটো ঘরের value অদলবদল (`a, b = b, a`) করতে হয়, তাহলে পুরো reverse টা just দুই প্রান্ত থেকে সেই swap বারবার করা — একটা index বাঁ দিক থেকে ডানে, আরেকটা ডান দিক থেকে বাঁয়ে।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা সরল mirror-সম্পর্ক: index `i`-এর element-এর জায়গা হওয়া উচিত index `n-1-i`-তে। তাই শুধু `i` আর `n-1-i` জোড়াগুলো swap করলেই হয়। আর invariant: যেকোনো মুহূর্তে `left`-এর বাঁ পাশ আর `right`-এর ডান পাশ ইতিমধ্যে চূড়ান্ত (final) জায়গায় বসে গেছে; মাঝের অংশটুকু এখনো বাকি।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না — array টা already আছে, আর শুধু **দুটো integer pointer** (`left`, `right`)। এটাই এর সৌন্দর্য: O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Array-র সবচেয়ে বড় superpower হলো index দিয়ে **O(1) random access** — `s[left]` আর `s[right]` দুটোতেই সরাসরি, সাথে সাথে পৌঁছানো যায় (concept.md-র mailbox analogy মনে করো)। তাই কোনো খোঁজাখুঁজি ছাড়াই দুই প্রান্তের ঘর ছুঁয়ে অদলবদল করা যায়। List mutable বলে in-place বদলানোও সম্ভব।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: একটা নতুন array নাও, পুরোনোটা শেষ থেকে শুরুর দিকে পড়ে নতুনটায় ভরো, তারপর copy করে ফেরত দাও।
```text
new = []
for i = n-1 down to 0:
new.append(s[i])
copy new back into s
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ঠিক উত্তর দেয়, কিন্তু **O(n) extra space** নেয় (নতুন array)। অথচ problem চায় in-place, O(1) extra space। পুরোটা copy করা অপচয় — array টা already হাতে আছে, শুধু ভেতরে দুই প্রান্তের জোড়া swap করলেই হয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **পুরো array একসাথে ওলটানোর দরকার নেই** — শুধু symmetric জোড়াগুলো (`i` আর `n-1-i`) swap করলেই হয়। আর প্রতিটা swap-এ একসাথে দুটো element তাদের final জায়গায় বসে যায়, তাই অর্ধেক পথ হাঁটলেই (`n/2` swap) পুরোটা reverse।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
দুটো pointer নাও — `left` শুরুতে 0, `right` শুরুতে `n-1`। যতক্ষণ `left < right`: দুটোর value swap করো, তারপর `left` এক ঘর ডানে, `right` এক ঘর বাঁয়ে। ওরা মাঝখানে দেখা করলেই কাজ শেষ।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "array উল্টাব" ভাবার বদলে ভাবো "দুই প্রান্ত থেকে ভেতরের দিকে এসে জোড়ায় জোড়ায় swap করব।" তখন নতুন array-র দরকারই থাকে না, আর কাজও অর্ধেকে নেমে আসে।
### ছবিতে বোঝা {#7-visual-explanation}
`["h","e","l","l","o"]` দিয়ে দুই pointer-এর নাচ:
```text
[ h e l l o ]
L R swap h,o -> [ o e l l h ]
L R swap e,l -> [ o l l e h ]
LR L == R, থামো
ফল: [ o l l e h ]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `["h","e","l","l","o"]` (n = 5):
1. শুরু: `left=0`, `right=4`। `left < right` → swap `s[0],s[4]` (h↔o)। array: `[o,e,l,l,h]`। `left=1`, `right=3`।
2. `left < right` → swap `s[1],s[3]` (e↔l)। array: `[o,l,l,e,h]`। `left=2`, `right=2`।
3. `left < right` মিথ্যা (2 < 2 নয়) → loop শেষ।
4. ফল: `[o,l,l,e,h]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def reverse_string(s):
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left] # দুই প্রান্ত swap
left += 1 # left ডানে
right -= 1 # right বাঁয়ে
return s
# ---- tests ----
assert reverse_string(["h", "e", "l", "l", "o"]) == ["o", "l", "l", "e", "h"]
assert reverse_string(["H", "a", "n", "n", "a", "h"]) == ["h", "a", "n", "n", "a", "H"]
assert reverse_string(["a"]) == ["a"] # একটা element
assert reverse_string([]) == [] # খালি array
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `left, right = 0, len(s) - 1` — দুই pointer array-র দুই প্রান্তে বসালাম।
- `while left < right:` — যতক্ষণ ওরা দেখা না করছে; সমান হলে মাঝের element নিজের জায়গাতেই থাকে, swap লাগে না।
- `s[left], s[right] = s[right], s[left]` — Python-এর tuple swap, কোনো temp variable ছাড়াই অদলবদল।
- `left += 1` / `right -= 1` — দুজনেই এক ঘর ভেতরে।
- `return s` — একই (mutated) array ফেরত।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`["h","e","l","l","o"]` → প্রথম swap h↔o, পরের swap e↔l, মাঝের `l` যেখানে আছে সেখানেই → `["o","l","l","e","h"]`, assert pass। বাকি case গুলোও pass। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
JS-এ string immutable, তাই Python-এর মতোই char-এর **array** in place উল্টাই — দুই প্রান্ত থেকে swap।
```javascript
// throwing assert — fail করলে থেমে error দেবে
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
function reverseString(s) {
let left = 0, right = s.length - 1;
while (left < right) {
[s[left], s[right]] = [s[right], s[left]]; // দুই প্রান্ত swap, temp ছাড়া
left++;
right--;
}
return s;
}
// ---- test cases (file-এর example + edge case) ----
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
assert(eq(reverseString(["h", "e", "l", "l", "o"]), ["o", "l", "l", "e", "h"]), "hello");
assert(eq(reverseString(["H", "a", "n", "n", "a", "h"]), ["h", "a", "n", "n", "a", "H"]), "Hannah");
assert(eq(reverseString(["a"]), ["a"]), "একটা element");
assert(eq(reverseString([]), []), "খালি array");
console.log("সব JS test pass!");
```
> **JS টীকা:** JS string immutable — `str[i] = ...` চলে না; তাই problem char-array চায় (`["h",...]`)। আস্ত string উল্টাতে হলে `str.split("").reverse().join("")`, কিন্তু সেটা O(n) extra space — in-place দুই-pointer-এর মূল শিক্ষা হারায়। swap-এ `[a, b] = [b, a]` (array destructuring), temp লাগে না।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function reverseString(s: string[]): string[] {
let left = 0, right = s.length - 1;
while (left < right) {
[s[left], s[right]] = [s[right], s[left]];
left++;
right--;
}
return s;
}
function expectArr(actual: string[], expected: string[], msg = ""): void {
if (JSON.stringify(actual) !== JSON.stringify(expected)) {
throw new Error(`FAIL ${msg}: [${actual}]`);
}
}
expectArr(reverseString(["h", "e", "l", "l", "o"]), ["o", "l", "l", "e", "h"], "hello");
expectArr(reverseString(["a"]), ["a"], "single");
expectArr(reverseString([]), [], "empty");
console.log("সব TS test pass!");
```
> **TS টীকা:** `s: string[]` declare করায় ভুলে একটা আস্ত `string` (যা JS-এ index করা গেলেও mutate হয় না) পাঠানো compile-time-এ আটকায় — in-place mutation-এর contract type-level-এই পরিষ্কার।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — প্রায় `n/2` বার swap হয়, প্রতিটা O(1); মোট O(n)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু দুটো integer pointer; array-র সাইজের সাথে extra memory বাড়ে না।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `while left <= right` লেখা — তখন মাঝের element নিজের সাথে নিজে swap হয় (ক্ষতি নেই, কিন্তু অপ্রয়োজনীয়); আসল ভুল হয় যদি এর সাথে pointer move ভুল করো।
- নতুন array বানিয়ে ফেরত দেওয়া — তখন আর "in place" থাকে না।
- `right = len(s)` দেওয়া (last index `len(s)-1`, `len(s)` নয়) → index out of range।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: array traversal + দুটো ঘরের swap। এই দুই-প্রান্ত swap-ই পরে rotate array (tracker #13)-এর triple-reversal-এর building block। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 4 — In-Place Reversal and Rotation" দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Rotate Array (তিনটা reversal) —