Problem link ও উৎস
- **Original source:** LeetCode — Rotate Image
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
- **Difficulty:** Medium
- **Pattern:** coordinate map (ঘর `(r, c)` কোথায় যায় তার সূত্র)
- **Basic idea inherited from:** — (এই শাখার স্বাধীন গোড়া)
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা `n × n` বর্গাকার matrix (2D তালিকা) দেওয়া। একে **90° ঘড়ির কাঁটার দিকে (clockwise)** ঘোরাতে হবে — যেমন একটা ছবি বা কাগজ হাতে নিয়ে ডান দিকে এক চতুর্থাংশ পাক দিলে যা হয়।
উদাহরণ:
```text
আগে: 90° clockwise পরে:
1 2 3 7 4 1
4 5 6 -> 8 5 2
7 8 9 9 6 3
```
লক্ষ করো — আগের **প্রথম সারি** `[1, 2, 3]` ঘোরার পরে **শেষ কলাম** (উপর থেকে নিচে `1, 2, 3`) হয়ে গেছে। আসল চ্যালেঞ্জ — কোন ঘরটা ঠিক কোথায় যায় সেই সূত্রটা বের করা, আর সম্ভব হলে **বাড়তি matrix না বানিয়ে** (in-place) ঘোরানো।
### Input ও output {#6-example-input-and-output}
```text
input matrix 90° CW output
-----------------------------------------------------------
[[1,2,3], [[7,4,1],
[4,5,6], [8,5,2],
[7,8,9]] [9,6,3]]
[[1,2], [[3,1],
[3,4]] [4,2]]
[[5]] [[5]] (1×1, অপরিবর্তিত)
[[1,2,3,4], [[13,9,5,1],
[5,6,7,8], [14,10,6,2],
[9,10,11,12], [15,11,7,3],
[13,14,15,16]] [16,12,8,4]]
```
মূল edge case: **`n = 1`** (একটা ঘর, ঘোরালেও একই), আর **জোড় বনাম বিজোড় n**। in-place কৌশলে n যাই হোক transpose + reverse একইভাবে খাটে; শুধু transpose-এ `j` শুরু করতে হয় `i + 1` থেকে (কর্ণের উপরের অর্ধ), নইলে দুবার swap হয়ে আসল matrix ফিরে আসে।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো একটা দাবার বোর্ড টেবিলে রাখা, আর তুমি বোর্ডটা হাতে নিয়ে 90° ডানদিকে ঘোরালে। আগে যে গুটিটা বোর্ডের উপর-বাঁ কোণে ছিল, ঘোরানোর পরে সেটা উপর-ডান কোণে চলে যায়। প্রতিটা গুটিই একটা নির্দিষ্ট, অনুমেয় নিয়মে নতুন ঘরে যায় — কেউ এলোমেলো লাফায় না।
সেই নিয়মটাই আমাদের সূত্র `(r, c) -> (c, n−1−r)`। আরেকভাবে ভাবো — তুমি বোর্ড না ঘুরিয়ে, প্রতিটা গুটি তুলে তুলে নতুন জায়গায় বসাচ্ছ। কোন গুটি কোথায় বসবে তা যদি আগে থেকে সূত্রে জানো, তাহলে আলাদা একটা খালি বোর্ড না এনেও (in-place) — চারটে গুটি একসাথে চক্রাকারে ঘুরিয়ে — পুরো বোর্ড ঘুরিয়ে ফেলা যায়। ঠিক যেন চারজন মানুষ গোল হয়ে দাঁড়িয়ে একসাথে এক ঘর ডানে সরে গেল।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা geometry শাখার একটা **স্বাধীন গোড়া** (tracker-এ "inherited from: —") — আগের কোনো নির্দিষ্ট problem-এর সরাসরি বর্ধিত রূপ নয়। তবে এর কেন্দ্রীয় চিন্তা — **coordinate transform / অক্ষ-ঘোরানো** — 121 (Manhattan 45° rotation)-এর সাথে দর্শনে আত্মীয়। সেখানে আমরা coordinate ঘুরিয়ে দূরত্ব সহজ করেছিলাম; এখানে coordinate ঘুরিয়ে পুরো গ্রিড নতুন করে সাজাচ্ছি।
নতুন যেটা যোগ হলো — discrete (পূর্ণসংখ্যা index) coordinate map, আর in-place রূপান্তরের কৌশল (transpose + reverse)। এই "একটা index-সূত্র দিয়ে পুরো গ্রিড নাড়ানো" চিন্তাটা image processing, game board, robotics-এ বারবার ফিরবে। তাই স্বাধীন হলেও এটা coordinate-geometry পরিবারের গুরুত্বপূর্ণ সদস্য।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল গাণিতিক সম্পর্ক — একটা ঘরের নতুন অবস্থানের সূত্র। `n × n` matrix-এ `(r, c)` ঘর (সারি r, কলাম c, 0 থেকে গোনা) 90° clockwise ঘোরালে যায়:
> **`(r, c) -> (c, n − 1 − r)`**
অর্থাৎ নতুন সারি = পুরোনো কলাম `c`, আর নতুন কলাম = `n − 1 − r`। কেন? clockwise ঘোরায় (ক) উপরের সারি ডান কলামে যায় (তাই নতুন কলাম পুরোনো সারির উপর নির্ভর — উল্টোভাবে, `n−1−r`), আর (খ) বাঁ কলাম উপরের সারিতে যায় (তাই নতুন সারি = পুরোনো কলাম `c`)।
এই এক সূত্র থেকেই দুটো বাস্তব রূপ: একটা **নতুন matrix-এ** সরাসরি `new[c][n−1−r] = old[r][c]`; আরেকটা **in-place** — দুই ধাপে: প্রথমে transpose (`(r,c) ↔ (c,r)`), তারপর প্রতিটা সারি reverse। দুই ধাপ মিলে ঠিক ওই coordinate map-ই বাস্তবায়িত হয়, কিন্তু O(1) বাড়তি জায়গায়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল ও পরিষ্কার চিন্তা — একটা নতুন `n × n` matrix নাও, প্রতিটা ঘরকে সূত্র মেনে নতুন জায়গায় বসাও:
```python
def rotate_new(matrix):
n = len(matrix)
res = [[0] * n for _ in range(n)]
for r in range(n):
for c in range(n):
res[c][n - 1 - r] = matrix[r][c] # (r,c) -> (c, n-1-r)
return res
```
এটা সরাসরি coordinate map প্রয়োগ করে, তাই নিশ্চিত ঠিক — asserts-এ এটাই reference। পড়তে সহজ, সব ঘর একবার করে ছোঁয়। (একে "brute" বলছি কারণ এটা বাড়তি O(n²) জায়গা নেয় — সমস্যাটা প্রায়ই in-place চায়।)
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সময়ের দিক থেকে এই সমাধান ঠিকই O(n²) (প্রতিটা ঘর একবার), যা অনিবার্য — n² ঘর পড়তেই হবে। আসল "খরচ" এখানে **জায়গা**: একটা পুরো নতুন `n × n` matrix, অর্থাৎ O(n²) বাড়তি স্মৃতি।
```text
n = 4000 হলে (16,000,000 ঘর):
নতুন matrix: আরও 16,000,000 ঘরের জায়গা (O(n^2) বাড়তি স্মৃতি)
in-place : O(1) বাড়তি জায়গা (আসল matrix-এই কাজ)
```
বড় matrix বা memory-সীমিত পরিবেশে এই বাড়তি copy বিলাসিতা। interview-তে প্রায়ই স্পষ্ট শর্ত থাকে "modify in-place, বাড়তি matrix ব্যবহার কোরো না" — তখন নতুন-matrix সমাধান গ্রহণযোগ্য নয়। সেই কারণেই transpose + reverse কৌশল।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল insight — coordinate map-টাকে **in-place** করা যায় দুই সহজ ধাপে: transpose, তারপর প্রতিটা সারি reverse। কোনো বাড়তি matrix লাগে না:
```python
def rotate_inplace(matrix):
n = len(matrix)
# ধাপ 1: transpose — কর্ণের উপরের অর্ধ swap
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# ধাপ 2: প্রতিটা সারি উল্টে দাও
for row in matrix:
row.reverse()
return matrix
```
কেন কাজ করে? transpose `(r,c)` কে `(c,r)`-এ নেয়; তারপর row reverse `(c, r)` কে `(c, n−1−r)`-এ নেয়। দুই মিলিয়ে `(r,c) -> (c, n−1−r)` — ঠিক 90° clockwise map। সময় O(n²) (অনিবার্য), জায়গা O(1) বাড়তি।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" — **matrix ঘোরানো মানে এলোমেলো কিছু না; এটা প্রতিটা ঘরের জন্য একটা নির্দিষ্ট index-সূত্র — `(r, c) -> (c, n−1−r)`। সূত্রটা ধরলে বাকিটা যান্ত্রিক।**
আর দ্বিতীয় tweak — সেই এক সূত্রকে দুটো সহজ, পরিচিত operation-এ ভাঙা যায়: **transpose ∘ reverse**। আলাদা করে "কোন ঘর কোথায়" মনে রাখার চেয়ে "transpose, তারপর প্রতি সারি উল্টাও" মনে রাখা সহজ, আর সেটা আপনাআপনি in-place। (anti-clockwise চাইলে: transpose, তারপর প্রতি **কলাম** reverse — অথবা সারি reverse তারপর transpose।) "matrix/গ্রিড ঘোরাও বা coordinate বদলাও" দেখলেই আগে index-সূত্র লেখো, তারপর সেটাকে চেনা ধাপে ভাঙো।
### ছবিতে বোঝা {#5-visual-explanation}
প্রথমে কোন ঘর কোথায় যায়, একটা ছবি (`n = 3`):
```text
আগে (r,c): 90° CW পরে: সূত্র (r,c)->(c, n-1-r), n=3
(0,0)(0,1)(0,2) (0,2)(1,2)(2,2) (0,0)->(0,2) (0,2)->(2,2)
(1,0)(1,1)(1,2) -> (0,1)(1,1)(2,1) (0,1)->(1,2) (1,0)->(0,1)
(2,0)(2,1)(2,2) (0,0)(1,0)(2,0) (2,0)->(0,0) ইত্যাদি
মান দিয়ে:
1 2 3 7 4 1
4 5 6 -> 8 5 2
7 8 9 9 6 3
```
in-place দুই-ধাপ কৌশল — transpose তারপর row reverse:
```text
আসল: ধাপ 1: transpose ধাপ 2: প্রতি সারি reverse
1 2 3 1 4 7 7 4 1
4 5 6 -> 2 5 8 -> 8 5 2
7 8 9 3 6 9 9 6 3
(r,c) <-> (c,r) (প্রতি সারি উল্টো)
দুই ধাপ একসাথে = (r,c) -> (c, n-1-r) (একই coordinate map, O(1) জায়গা)
```
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`matrix = [[1,2],[3,4]]` (n=2) in-place ঘোরাই:
1. শুরু: `[[1, 2], [3, 4]]`।
2. **transpose** — শুধু `i < j` ঘর swap, এখানে `(0,1) ↔ (1,0)`: `matrix[0][1]`(=2) আর `matrix[1][0]`(=3) বদল → `[[1, 3], [2, 4]]`।
3. **row reverse** — সারি 0 `[1, 3]` উল্টে `[3, 1]`; সারি 1 `[2, 4]` উল্টে `[4, 2]` → `[[3, 1], [4, 2]]`।
4. শেষ: `[[3, 1], [4, 2]]`।
যাচাই: সূত্রে `(0,0)=1 -> (0, n−1−0)=(0,1)`, তাই নতুন `[0][1]` = 1 ✓; `(0,1)=2 -> (1,1)`, নতুন `[1][1]` = 2 ✓। নতুন-matrix reference-ও `[[3,1],[4,2]]` দেয় — মিলে গেল।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
import copy
def rotate_new(matrix):
"""নতুন matrix-এ 90° clockwise ঘোরায় (সূত্র সরাসরি)। O(n^2) সময়, O(n^2) জায়গা।"""
n = len(matrix)
res = [[0] * n for _ in range(n)]
for r in range(n):
for c in range(n):
res[c][n - 1 - r] = matrix[r][c] # (r,c) -> (c, n-1-r)
return res
def rotate_inplace(matrix):
"""আসল matrix-এই 90° clockwise ঘোরায় (transpose + row reverse)। O(n^2) সময়, O(1) বাড়তি।"""
n = len(matrix)
for i in range(n): # ধাপ 1: transpose
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for row in matrix: # ধাপ 2: প্রতি সারি reverse
row.reverse()
return matrix
def map_coord(r, c, n):
"""ঘর (r,c) 90° CW ঘোরালে নতুন (সারি, কলাম)।"""
return (c, n - 1 - r)
# --- হাতে বাছা test (নতুন ও in-place দুটো একই ফল) ---
m1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
exp1 = [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
assert rotate_new(m1) == exp1
assert rotate_inplace(copy.deepcopy(m1)) == exp1
m2 = [[1, 2], [3, 4]]
exp2 = [[3, 1], [4, 2]]
assert rotate_new(m2) == exp2
assert rotate_inplace(copy.deepcopy(m2)) == exp2
assert rotate_new([[5]]) == [[5]]
assert rotate_inplace([[5]]) == [[5]]
# coordinate map যাচাই
assert map_coord(0, 0, 3) == (0, 2)
assert map_coord(2, 0, 3) == (0, 0)
assert map_coord(1, 2, 3) == (2, 1)
# --- cross-check: in-place == নতুন == coordinate map (random) ---
import random
random.seed(2)
for _ in range(3000):
n = random.randint(1, 6)
m = [[random.randint(0, 99) for _ in range(n)] for _ in range(n)]
new_way = rotate_new(m)
inplace = rotate_inplace(copy.deepcopy(m))
assert new_way == inplace, m
# সূত্র সরাসরি যাচাই: আসল (r,c) মান নতুন (c, n-1-r)-এ আছে কি
for r in range(n):
for c in range(n):
nr, nc = map_coord(r, c, n)
assert new_way[nr][nc] == m[r][c]
print(rotate_inplace([[1, 2, 3], [4, 5, 6], [7, 8, 9]])) # [[7,4,1],[8,5,2],[9,6,3]]
print(map_coord(0, 0, 3)) # (0, 2)
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
res[c][n - 1 - r] = matrix[r][c]
```
coordinate map-এর সরাসরি প্রয়োগ — পুরোনো `(r, c)` ঘরের মান নতুন matrix-এর `(c, n−1−r)` ঘরে বসছে। এই এক লাইনই পুরো ঘোরানোর সংজ্ঞা।
```text
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
```
transpose — `(i, j)` আর `(j, i)` ঘর swap। `j` শুরু `i + 1` থেকে, যাতে শুধু কর্ণের **উপরের** অর্ধ ছোঁয়া হয়; `j` 0 থেকে শুরু করলে প্রতিটা জোড়া দুবার swap হয়ে আসল matrix ফিরে আসত (ভুল)। কর্ণের ঘর (`i == j`) নিজের জায়গাতেই থাকে, তাই বাদ।
```text
for row in matrix: row.reverse()
```
প্রতিটা সারি উল্টে দেওয়া। transpose-এর পর এটা প্রতিটা `(c, r)` কে `(c, n−1−r)`-এ নেয় — ফলে সম্পূর্ণ 90° clockwise। এটাই in-place হওয়ার চাবি (নতুন matrix লাগে না)।
```text
def map_coord(r, c, n): return (c, n - 1 - r)
```
শুধু একটা ঘরের গন্তব্য জানার সূত্র — যখন পুরো matrix না, নির্দিষ্ট বিন্দুর নতুন অবস্থান দরকার (যেমন game-এ একটা গুটি কোথায় যাবে)।
cross-check অংশে 3000টা random matrix-এ তিন রাস্তা (নতুন, in-place, সূত্র) একে অপরের সাথে মিলিয়ে দেখা — সব মিললে `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
(0, 2)
সব test pass!
```
প্রথম লাইন: `[[1,2,3],[4,5,6],[7,8,9]]` in-place ঘোরানোর ফল — `[[7,4,1],[8,5,2],[9,6,3]]` (section 1-এর ছবির সাথে মেলে)। দ্বিতীয়: `map_coord(0,0,3)` = `(0, 2)` — উপর-বাঁ ঘর উপর-ডানে গেল। তার আগের সব `assert` (হাতে বাছা + 3000টা random cross-check, সূত্রসহ) চুপচাপ pass। সবশেষে `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n²)** — দুই রাস্তাতেই প্রতিটা ঘর ধ্রুবক বার ছোঁয়া হয় (n² ঘর)। এটা অনিবার্য, কারণ সব ঘর অন্তত একবার পড়তে/লিখতে হবে। (transpose O(n²/2) + reverse O(n²/2) = O(n²)।)
### অতিরিক্ত জায়গা {#16-space-complexity}
`rotate_new`: **O(n²)** — একটা পুরো নতুন matrix। `rotate_inplace`: **O(1)** বাড়তি — আসল matrix-এই swap ও reverse, কোনো নতুন 2D array লাগে না (শুধু swap-এ এক temp variable)। interview-তে in-place সমাধানই কাঙ্ক্ষিত।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **transpose-এ `j` 0 থেকে শুরু** — তাহলে প্রতি জোড়া দুবার swap হয়ে আসল matrix ফিরে আসে; `j = i + 1` থেকে শুরু করো (উপরের ত্রিভুজ)।
2. **clockwise/anti-clockwise গুলিয়ে ফেলা** — CW = transpose + **row** reverse; CCW = transpose + **column** reverse (বা row reverse তারপর transpose)। দিক মিলিয়ে নাও।
3. **সূত্রে চিহ্ন ভুল** — সঠিক `(r, c) -> (c, n−1−r)`। `n−1−c` বা `(n−1−c, r)` লিখলে ভুল দিক/অবস্থান।
4. **non-square ধরে নেওয়া** — এই in-place transpose শুধু `n × n`-এ খাটে; আয়তাকার matrix-এ মাত্রা বদলায়, তখন নতুন matrix লাগে।
5. **নতুন matrix বানিয়ে original-এ assign না করা** — সমস্যা যদি in-place চায়, `matrix = rotate_new(matrix)` কাজ করবে না (caller-এর reference বদলায় না); সরাসরি ভেতরের মান বদলাও।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Rotate Image** (