122 — Rotate Matrix and Coordinates

এই problem-টা দেখায় একটা matrix 90° ঘোরানো আসলে শুধু একটা coordinate map — "কোন ঘর কোথায় যায়" তার একটা সরল সূত্র। সূত্রটা একবার বুঝে গেলে শুধু matrix নয়, যেকোনো coordinate ঘোরানো (game board, image, robot grid) তোমার কাছে সহজ হয়ে যাবে। আর একটা bonus: এই ঘোরানো কোনো বাড়তি জায়গা ছাড়াই (in-place) করা যায় — সেটাও শিখব। Geometry-তে মনে রেখো: ছবি না এঁকে code লেখা নিষেধ।

Problem link ও উৎস

• Original source: LeetCode — Rotate Image
• Platform: LeetCode — https://leetcode.com/problems/rotate-image/
• Topic: Math-based programming fundamentals → Level 9: Geometry & Coordinate Math
• Difficulty: Medium
• Pattern: coordinate map (ঘর (r, c) কোথায় যায় তার সূত্র)
• Basic idea inherited from: — (এই শাখার স্বাধীন গোড়া)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

একটা n × n বর্গাকার matrix (2D তালিকা) দেওয়া। একে 90° ঘড়ির কাঁটার দিকে (clockwise) ঘোরাতে হবে — যেমন একটা ছবি বা কাগজ হাতে নিয়ে ডান দিকে এক চতুর্থাংশ পাক দিলে যা হয়।

উদাহরণ:

উদাহরণ

আগে:            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

উদাহরণ

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 ফিরে আসে।

চেনা উদাহরণে বোঝা

ভাবো একটা দাবার বোর্ড টেবিলে রাখা, আর তুমি বোর্ডটা হাতে নিয়ে 90° ডানদিকে ঘোরালে। আগে যে গুটিটা বোর্ডের উপর-বাঁ কোণে ছিল, ঘোরানোর পরে সেটা উপর-ডান কোণে চলে যায়। প্রতিটা গুটিই একটা নির্দিষ্ট, অনুমেয় নিয়মে নতুন ঘরে যায় — কেউ এলোমেলো লাফায় না।

সেই নিয়মটাই আমাদের সূত্র (r, c) -> (c, n−1−r)। আরেকভাবে ভাবো — তুমি বোর্ড না ঘুরিয়ে, প্রতিটা গুটি তুলে তুলে নতুন জায়গায় বসাচ্ছ। কোন গুটি কোথায় বসবে তা যদি আগে থেকে সূত্রে জানো, তাহলে আলাদা একটা খালি বোর্ড না এনেও (in-place) — চারটে গুটি একসাথে চক্রাকারে ঘুরিয়ে — পুরো বোর্ড ঘুরিয়ে ফেলা যায়। ঠিক যেন চারজন মানুষ গোল হয়ে দাঁড়িয়ে একসাথে এক ঘর ডানে সরে গেল।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা 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 পরিবারের গুরুত্বপূর্ণ সদস্য।

ভেতরের অঙ্ক

মূল গাণিতিক সম্পর্ক — একটা ঘরের নতুন অবস্থানের সূত্র। 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) বাড়তি জায়গায়।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সবচেয়ে সরল ও পরিষ্কার চিন্তা — একটা নতুন 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 চায়।)

কোথায় বেশি কাজ হতে পারে

সময়ের দিক থেকে এই সমাধান ঠিকই O(n²) (প্রতিটা ঘর একবার), যা অনিবার্য — n² ঘর পড়তেই হবে। আসল "খরচ" এখানে জায়গা: একটা পুরো নতুন n × n matrix, অর্থাৎ O(n²) বাড়তি স্মৃতি।

উদাহরণ

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 কৌশল।

আরও ভালোভাবে ভাবা

মূল 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) বাড়তি।

ভাবনার পরিবর্তন

আসল "আহা!" — matrix ঘোরানো মানে এলোমেলো কিছু না; এটা প্রতিটা ঘরের জন্য একটা নির্দিষ্ট index-সূত্র — (r, c) -> (c, n−1−r)। সূত্রটা ধরলে বাকিটা যান্ত্রিক।

আর দ্বিতীয় tweak — সেই এক সূত্রকে দুটো সহজ, পরিচিত operation-এ ভাঙা যায়: transpose ∘ reverse। আলাদা করে "কোন ঘর কোথায়" মনে রাখার চেয়ে "transpose, তারপর প্রতি সারি উল্টাও" মনে রাখা সহজ, আর সেটা আপনাআপনি in-place। (anti-clockwise চাইলে: transpose, তারপর প্রতি কলাম reverse — অথবা সারি reverse তারপর transpose।) "matrix/গ্রিড ঘোরাও বা coordinate বদলাও" দেখলেই আগে index-সূত্র লেখো, তারপর সেটাকে চেনা ধাপে ভাঙো।

ছবিতে বোঝা

প্রথমে কোন ঘর কোথায় যায়, একটা ছবি (n = 3):

উদাহরণ

আগে (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:

উদাহরণ

আসল:        ধাপ 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-এ ধাপে ধাপে

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]] দেয় — মিলে গেল।

কোড ও ব্যাখ্যা

Python

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!")

কোডের প্রতিটি অংশ

উদাহরণ

res[c][n - 1 - r] = matrix[r][c]

coordinate map-এর সরাসরি প্রয়োগ — পুরোনো (r, c) ঘরের মান নতুন matrix-এর (c, n−1−r) ঘরে বসছে। এই এক লাইনই পুরো ঘোরানোর সংজ্ঞা।

উদাহরণ

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) নিজের জায়গাতেই থাকে, তাই বাদ।

উদাহরণ

for row in matrix: row.reverse()

প্রতিটা সারি উল্টে দেওয়া। transpose-এর পর এটা প্রতিটা (c, r) কে (c, n−1−r)-এ নেয় — ফলে সম্পূর্ণ 90° clockwise। এটাই in-place হওয়ার চাবি (নতুন matrix লাগে না)।

উদাহরণ

def map_coord(r, c, n): return (c, n - 1 - r)

শুধু একটা ঘরের গন্তব্য জানার সূত্র — যখন পুরো matrix না, নির্দিষ্ট বিন্দুর নতুন অবস্থান দরকার (যেমন game-এ একটা গুটি কোথায় যাবে)।

cross-check অংশে 3000টা random matrix-এ তিন রাস্তা (নতুন, in-place, সূত্র) একে অপরের সাথে মিলিয়ে দেখা — সব মিললে সব test pass!।

Output মিলিয়ে দেখা

চালালে যা ছাপবে:

উদাহরণ

[[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!।

খরচ ও সাধারণ ভুল

সময়

O(n²) — দুই রাস্তাতেই প্রতিটা ঘর ধ্রুবক বার ছোঁয়া হয় (n² ঘর)। এটা অনিবার্য, কারণ সব ঘর অন্তত একবার পড়তে/লিখতে হবে। (transpose O(n²/2) + reverse O(n²/2) = O(n²)।)

অতিরিক্ত জায়গা

rotate_new: O(n²) — একটা পুরো নতুন matrix। rotate_inplace: O(1) বাড়তি — আসল matrix-এই swap ও reverse, কোনো নতুন 2D array লাগে না (শুধু swap-এ এক temp variable)। interview-তে in-place সমাধানই কাঙ্ক্ষিত।

যে ভুলগুলো এড়াতে হবে

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 বদলায় না); সরাসরি ভেতরের মান বদলাও।

শেখা ও পরের অনুশীলন

এই ধারণার পরের অনুশীলন

• LeetCode — Rotate Image (https://leetcode.com/problems/rotate-image/) — এটাই মূল problem; in-place 90° ঘোরানো।
• LeetCode — Spiral Matrix (https://leetcode.com/problems/spiral-matrix/) — coordinate-পথ ধরে matrix পড়া; index-সূত্রের আরেক প্রয়োগ।
• LeetCode — Set Matrix Zeroes (https://leetcode.com/problems/set-matrix-zeroes/) — in-place matrix manipulation, O(1) জায়গার কৌশল একই পরিবার।

কৌশলটি মনে রাখুন

Coordinate map for rotation (transpose + reverse) — 90° clockwise = ঘর (r, c) -> (c, n−1−r); in-place বাস্তবায়ন = transpose তারপর প্রতিটা সারি reverse, O(1) বাড়তি জায়গায়। বড় শিক্ষা: গ্রিড ঘোরানো/coordinate বদলানো এলোমেলো নয় — আগে "কোন index কোথায় যায়" সূত্রটা লেখো, তারপর সেটাকে চেনা operation (transpose, reverse) দিয়ে in-place বানাও।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে এক লাইনে: "Rotate matrix 90° CW = (r,c)→(c, n−1−r); in-place = transpose + প্রতি সারি reverse (O(1) জায়গা)। Signal: 'matrix/গ্রিড ঘোরাও' দেখলেই আগে index-সূত্র, তারপর transpose∘reverse মনে পড়ুক। CCW হলে column reverse। transpose-এ j শুরু i+1 থেকে।"

পরের ধাপ → 123 — Grid Movement Math (গ্রিডে চলন ও parity)। ভিত্তি/সম্পর্কিত → 121 — Manhattan Distance Tricks (আরেক রকম coordinate রূপান্তর)।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখো; problem statement copy কোরো না; official link শুধু attribution-এর জন্য রাখো; "asked by Google/Amazon" এমন দাবি কোরো না — বরং "Google-style pattern" / "common interview pattern" লেখো।