Problem link ও উৎস
- **Original source:** Classic in-place rotation exercise
- **Platform:** LeetCode —
- **Topic:** array
- **Difficulty:** Medium
- **Pattern:** triple reversal (তিনবার reverse করে O(1) space rotation)
- **Basic idea inherited from:** in-place reversal (problem 1) — দুই প্রান্ত থেকে swap করে একটা অংশ উল্টানো
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array `nums` আর একটা সংখ্যা `k` দেওয়া। array-কে **ডানে `k` ঘর** rotate করতে হবে, অর্থাৎ শেষের `k`-টা element সামনে চলে আসবে আর বাকিরা পিছিয়ে যাবে। শর্ত: কাজটা **in place** করো, O(1) extra space-এ।
```text
nums = [1, 2, 3, 4, 5, 6, 7], k = 3
শেষের 3-টা (5,6,7) সামনে আসবে
ফল: [5, 6, 7, 1, 2, 3, 4]
```
### Input ও output {#8-example-input-and-output}
```text
Input : [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]
Input : [-1,-100,3,99], k=2 -> [3,99,-1,-100]
Edge case 1 (k > n): [1,2], k=3 -> [2,1] (k%n = 1, ডানে 1 ঘর)
Edge case 2 (খালি): [], k=2 -> []
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
একসারি তাসের কথা ভাবো। ডানের কয়েকটা তাস সামনে আনতে চাও। প্রথমে পুরো সারি উল্টে দাও (এখন ডানেরগুলো বাঁয়ে, কিন্তু নিজেদের মধ্যে উল্টো)। তারপর বাঁয়ের ওই কয়েকটা আলাদা করে আবার উল্টাও আর ডানের বাকিগুলোও আলাদা করে উল্টাও — প্রতিটা গুচ্ছ আবার সোজা হয়ে গেল, অথচ দুই গুচ্ছ জায়গা বদলেছে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত **in-place reversal** (problem 1)। reverse-এ যেমন দুই প্রান্ত থেকে swap করে একটা অংশ উল্টানো হয়, এখানে সেই reverse-কেই building block বানিয়ে তিনবার ডাকা হয়। কোনো temporary array লাগে না — শুধু দুই-প্রান্ত swap-এর পুনর্ব্যবহার। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 4 — In-Place Reversal and Rotation" দেখো।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: পুরো array reverse করলে শেষের `k`-টা element সামনে চলে আসে, কিন্তু উল্টো order-এ; আবার মাঝখানে দুই block-এর ভেতরের order-ও উল্টে যায়। তাই (1) পুরোটা reverse, (2) প্রথম `k`-টা reverse করে তাদের order ঠিক, (3) বাকি `n-k`-টা reverse করে তাদের order ঠিক — সব মিলিয়ে block দুটো জায়গা বদলায় কিন্তু ভেতরের order forward থাকে। আর `k %= n`, কারণ `n` ঘর rotate মানে কিছুই না বদলানো।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
কোনো extra data structure লাগে না — array-টা already আছে, আর reverse-এর জন্য **দুটো integer pointer**। O(1) extra space।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
Array mutable আর O(1) random access — তাই যেকোনো sub-range-এর দুই প্রান্ত সরাসরি ছুঁয়ে swap করা যায়। তিনটা reverse মিলিয়ে rotation হয়ে যায় কোনো নতুন array না বানিয়ে, যা problem-এর O(1) space দাবি মেটায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: একটা নতুন array নাও, প্রতিটা element-কে তার নতুন জায়গায় (`(i + k) % n`) বসাও, তারপর copy করে ফেরত দাও।
```text
res = new array size n
for i in range(n):
res[(i + k) % n] = nums[i]
copy res back into nums
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
এটা ঠিক উত্তর দেয়, কিন্তু **O(n) extra space** (নতুন array) নেয়, অথচ problem চায় O(1)। আরেকটা সরল উপায় — একবারে এক ঘর করে `k` বার rotate — সেটা **O(n*k)** time, k বড় হলে ভয়ংকর ধীর।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: reversal দিয়ে rotation করা যায়। পুরো array reverse করলে দুই block জায়গা বদলায় (কিন্তু ভেতরে উল্টো); তারপর দুই block আলাদা করে reverse করলে ভেতরের order ঠিক হয়ে যায়। অর্থাৎ rotation = তিনটা reversal, কোনো temp array ছাড়াই।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
আগে `k %= n` করো (k বড় হলেও সামলায়, আর n ঘর rotate = identity)। তারপর তিনটা reverse: পুরোটা `[0, n-1]`, এরপর `[0, k-1]`, এরপর `[k, n-1]`। প্রতিটা reverse দুই-প্রান্ত swap, সব মিলিয়ে O(n) time, O(1) space।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "rotate করতে নিশ্চয়ই temporary array লাগবে" ভাবার বদলে মনে করো "দুইবার reverse করলে একটা block আবার সোজা হয়, কিন্তু জায়গা বদলে ফেলে।" তখন শুধু in-place reverse-ই যথেষ্ট।
### ছবিতে বোঝা {#7-visual-explanation}
`nums = [1, 2, 3, 4, 5, 6, 7]`, `k = 3`:
```text
reverse all: [7, 6, 5, 4, 3, 2, 1]
reverse first k=3: [5, 6, 7, 4, 3, 2, 1]
reverse last n-k=4: [5, 6, 7, 1, 2, 3, 4] <- done
শেষের 3-টা সামনে এসে গেছে, প্রতিটা গুচ্ছ আবার forward order-এ
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[-1, -100, 3, 99]`, `k = 2` (`n = 4`, `k % n = 2`):
1. reverse পুরোটা `[0,3]`: `[99, 3, -100, -1]`।
2. reverse প্রথম `k=2` `[0,1]`: `[3, 99, -100, -1]`।
3. reverse বাকি `[2,3]`: `[3, 99, -1, -100]`।
4. ফল: `[3, 99, -1, -100]`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def rotate(nums, k):
n = len(nums)
if n == 0:
return nums
k %= n # k > n হলেও ঠিক; n ঘর rotate = কিছু না
def reverse(lo, hi):
while lo < hi:
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
reverse(0, n - 1) # পুরোটা উল্টাও
reverse(0, k - 1) # প্রথম k উল্টাও
reverse(k, n - 1) # বাকিটা উল্টাও
return nums
# ---- tests ----
assert rotate([1, 2, 3, 4, 5, 6, 7], 3) == [5, 6, 7, 1, 2, 3, 4]
assert rotate([-1, -100, 3, 99], 2) == [3, 99, -1, -100]
assert rotate([1, 2], 3) == [2, 1] # k > n
assert rotate([1], 0) == [1] # k = 0
assert rotate([], 2) == [] # খালি
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if n == 0: return nums` — খালি array-তে কিছু করার নেই (`k %= 0` crash এড়াতেও জরুরি)।
- `k %= n` — `k` বড় হলে wrap করে; `n` ঘর rotate মানে অপরিবর্তিত, তাই modulo।
- `def reverse(lo, hi)` — দুই-প্রান্ত swap করে `[lo, hi]` অংশ উল্টায় (problem 1-এর সেই reverse)।
- `reverse(0, n-1)` — পুরো array উল্টানো।
- `reverse(0, k-1)` — সামনে আসা block-এর order ঠিক করা।
- `reverse(k, n-1)` — পিছনে যাওয়া block-এর order ঠিক করা।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`[1..7], k=3` → তিনটা reverse-এর পর `[5,6,7,1,2,3,4]`, assert pass। `[-1,-100,3,99], k=2` → `[3,99,-1,-100]`; `[1,2], k=3` → `k%2=1`, ডানে 1 ঘর `[2,1]`; `[1], k=0` → `k%1=0`, সব reverse no-op `[1]`; `[]` → early return `[]`। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
তিনটা in-place reverse দিয়ে rotation — array equality test-এ `JSON.stringify`।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);
// rotate right by k, in place (triple reversal)
function rotate(nums, k) {
const n = nums.length;
if (n === 0) return nums;
k %= n; // k > n হলেও ঠিক; n ঘর rotate = কিছু না
const reverse = (lo, hi) => {
while (lo < hi) {
[nums[lo], nums[hi]] = [nums[hi], nums[lo]];
lo++; hi--;
}
};
reverse(0, n - 1); // পুরোটা উল্টাও
reverse(0, k - 1); // প্রথম k উল্টাও
reverse(k, n - 1); // বাকিটা উল্টাও
return nums;
}
// ---- test cases (example + edge) ----
assert(eq(rotate([1, 2, 3, 4, 5, 6, 7], 3), [5, 6, 7, 1, 2, 3, 4]), "k=3");
assert(eq(rotate([-1, -100, 3, 99], 2), [3, 99, -1, -100]), "negatives");
assert(eq(rotate([1, 2], 3), [2, 1]), "k>n"); // edge
assert(eq(rotate([1], 0), [1]), "k=0");
assert(eq(rotate([], 2), []), "empty"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** array সমান কিনা `===` দিয়ে যাচাই হয় না (reference compare), তাই `JSON.stringify(a) === JSON.stringify(b)`। swap-এ destructuring `[a, b] = [b, a]` idiomatic। `n === 0` guard আগে রাখো, নইলে `k %= 0` দিলে `NaN`।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
function rotate(nums: number[], k: number): number[] {
const n = nums.length;
if (n === 0) return nums;
k %= n;
const reverse = (lo: number, hi: number): void => {
while (lo < hi) {
[nums[lo], nums[hi]] = [nums[hi], nums[lo]];
lo++; hi--;
}
};
reverse(0, n - 1);
reverse(0, k - 1);
reverse(k, n - 1);
return nums;
}
function expectArr(actual: number[], exp: number[], msg = ""): void {
if (JSON.stringify(actual) !== JSON.stringify(exp))
throw new Error(`FAIL ${msg}: got ${JSON.stringify(actual)}`);
}
expectArr(rotate([1, 2, 3, 4, 5, 6, 7], 3), [5, 6, 7, 1, 2, 3, 4], "k=3");
expectArr(rotate([1, 2], 3), [2, 1], "k>n");
expectArr(rotate([], 2), [], "empty");
console.log("সব TS test pass!");
```
> **TS টীকা:** `nums: number[]` আর return `number[]` declare করায় helper `expectArr` শুধু সঠিক type-এর array গ্রহণ করে; nested reverse closure-এ `lo`/`hi`-ও `number` বলে index ভুল হওয়ার সুযোগ নেই।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — তিনটা reverse মিলিয়ে প্রতিটা element ধ্রুবসংখ্যকবার swap হয়।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(1)** — শুধু reverse-এর দুটো pointer; কোনো extra array নয়।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- `k %= n` ভুলে যাওয়া — `k >= n` হলে `reverse(0, k-1)` index out of range বা ভুল ফল দেবে।
- খালি array-তে `k %= n` করা — `n = 0` হলে ZeroDivisionError; আগে `n == 0` check করো।
- reverse-এর order বা সীমানা গুলিয়ে ফেলা — মনে রাখো: পুরোটা, তারপর প্রথম `k`, তারপর বাকি `n-k`।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: in-place two-pointer reversal (Reverse String #1)। সেই reverse-ই এখানে তিনবার ডাকা হয়। chapter-এর [../patterns.md](../patterns.md)-এর "Pattern 4 — In-Place Reversal and Rotation" দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Reverse String (একটাই reverse) —