48. Rotate Image

題目 / Problem

中文： 給定一個 n x n 的二維矩陣 matrix，代表一張圖片，請將這張圖片順時針旋轉 90 度。你必須原地旋轉（in-place），也就是直接修改傳入的矩陣本身，不可以另外開一個新的二維矩陣來裝結果。

English: You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees clockwise. You must do this in-place — modify the input matrix directly. Do not allocate a second 2D matrix to hold the result.

Constraints / 限制： - n == matrix.length == matrix[i].length（矩陣是正方形 / the matrix is square） - 1 <= n <= 20 - -1000 <= matrix[i][j] <= 1000

Worked example / 範例：

Input:  [[1,2,3],
         [4,5,6],
         [7,8,9]]

Output: [[7,4,1],
         [8,5,2],
         [9,6,3]]

原本第一列 1,2,3 旋轉後變成最後一行（從上往下 1,4,7... 不，是 1 跑到右上角）。簡單說：原本最上面那一橫排，旋轉後變成最右邊那一直排。 The top row 1,2,3 becomes the rightmost column after rotation.

名詞解釋 / Glossary

• 矩陣 / matrix：一個二維表格，用 matrix[row][col] 取值，row 是第幾列（橫排），col 是第幾行（直排）。A 2D grid of numbers; matrix[row][col] reads the value at a given row and column.
• 原地修改 / in-place：不開新的二維陣列，只用常數額外空間（最多幾個暫存變數），直接改原矩陣。Modifying the input directly using only O(1) extra memory — no second grid allowed.
• 轉置 / transpose：把矩陣沿著「主對角線」（從左上到右下）翻折，也就是把 matrix[i][j] 和 matrix[j][i] 互換，等於把列變成行。Reflecting the matrix across its main diagonal: swap matrix[i][j] with matrix[j][i], turning rows into columns.
• 主對角線 / main diagonal：從左上角 (0,0) 連到右下角 (n-1,n-1) 的那條斜線上的元素，這些元素在轉置時不動。The diagonal from top-left to bottom-right; these elements stay put during transpose.
• 水平翻轉每一列 / reverse each row：把每一橫排的元素左右顛倒（第一個跟最後一個交換，依此類推）。Flipping each row left-to-right (first element swaps with last, and so on).
• 交換 / swap：把兩個變數的值互換，通常借助一個暫存變數 tmp。Exchanging the values of two variables, usually via a temporary.

思路

中文： 最直覺的「暴力」做法是：另外開一個 n x n 的新矩陣 res，然後套公式 res[j][n-1-i] = matrix[i][j]（順時針旋轉的位置對應），最後把 res 複製回去。這完全正確，但題目明確規定不能另開二維矩陣，所以這個做法不符合要求，我們需要一個只用常數額外空間的辦法。

關鍵觀察是：順時針旋轉 90 度 = 先轉置，再把每一列左右翻轉。為什麼？轉置會把 matrix[i][j] 和 matrix[j][i] 互換（沿主對角線鏡射），這一步會把「列」變成「行」，但方向是反的；接著把每一列左右翻轉，就能把方向修正成順時針的結果。你也可以反過來理解：先轉置再左右翻，等價於旋轉公式 new[i][j] = old[n-1-j][i]，動手推一兩個座標就會發現完全吻合。

這兩步都能原地完成。轉置時，我們只交換主對角線上方的元素（j 從 i+1 開始），因為交換 (i,j) 的同時就處理了 (j,i)，若整個掃過去會把已經換好的又換回來。左右翻轉時，對每一列用「頭尾雙指針」往中間靠攏，互相交換。整個過程只用到一個暫存變數 tmp，空間是 O(1)，符合原地的要求。

English: The brute-force idea is to allocate a fresh n x n matrix res, copy each value to its rotated position with res[j][n-1-i] = matrix[i][j], then copy res back. It's correct, but the problem forbids allocating a second 2D matrix, so we need an O(1)-space approach.

The key insight: a 90° clockwise rotation equals a transpose followed by reversing each row. Transposing swaps matrix[i][j] with matrix[j][i] (a mirror across the main diagonal), which converts rows into columns but in the wrong horizontal direction. Reversing each row then flips that direction into the correct clockwise result. Concretely, transpose-then-reverse matches the rotation formula new[i][j] = old[n-1-j][i] — trace a couple of coordinates and you'll see they line up.

Both steps run in place. For the transpose we only swap elements above the main diagonal (j starts at i+1): swapping (i,j) already fixes (j,i) too, so scanning the whole grid would undo our own work. For the row reversal we use a two-pointer approach per row — one index from the front, one from the back, swapping and walking toward the middle. The only extra storage is a single tmp variable, so space is O(1) as required.

逐步走查 / Walkthrough

我們用 [[1,2,3],[4,5,6],[7,8,9]]，n = 3。

Step 1 — 轉置 / Transpose (只交換主對角線上方的格子 / only swap above the diagonal):

對角線元素 1,5,9 全程沒動 / the diagonal 1,5,9 never moves.

Step 2 — 每列左右翻轉 / Reverse each row (頭尾雙指針 / two pointers per row):

中間元素 4,5,6 因為頭尾指針相遇所以不用換 / the middle elements stay put as the two pointers meet.

最終結果 / Final: [[7,4,1],[8,5,2],[9,6,3]] ✅ 與預期輸出一致 / matches the expected output.

Solution — C

// 演算法 / Algorithm:
// 順時針旋轉 90 度 = 先轉置（沿主對角線鏡射），再把每一列左右翻轉。
// Clockwise 90° rotation = transpose (mirror across the main diagonal),
// then reverse each row. Done in place with O(1) extra space.

// LeetCode 的 C 簽名：matrix 是指向「int* 陣列」的指標，matrixSize 是列數 n，
// matrixColSize 指向「每列行數」的陣列（本題每列都是 n）。
// LeetCode's C signature: matrix is an array of int* rows; matrixSize is n;
// matrixColSize points to per-row column counts (all n here).
void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    int n = matrixSize;                    // n 是矩陣邊長 / n is the side length

    // ---- Step 1: 轉置 / transpose ----
    // 外層 i 從 0 到 n-1，代表目前處理的列 / outer loop i = current row
    for (int i = 0; i < n; i++) {
        // 內層 j 從 i+1 開始：只碰主對角線上方，避免換兩次又換回來。
        // j starts at i+1: only touch cells above the diagonal so we don't
        // swap the same pair twice (which would cancel out).
        for (int j = i + 1; j < n; j++) {
            int tmp = matrix[i][j];        // 暫存 (i,j) 的值 / save matrix[i][j]
            matrix[i][j] = matrix[j][i];   // (i,j) 換成對稱位置的值 / copy mirror in
            matrix[j][i] = tmp;            // 對稱位置填回原值，完成交換 / write back
        }
    }

    // ---- Step 2: 每一列左右翻轉 / reverse each row ----
    for (int i = 0; i < n; i++) {
        int left = 0;                      // 頭指針，指向該列最左 / front pointer
        int right = n - 1;                 // 尾指針，指向該列最右 / back pointer
        // 兩指針往中間靠攏，相遇就停 / walk toward the middle until they meet
        while (left < right) {
            int tmp = matrix[i][left];     // 暫存最左值 / save the left value
            matrix[i][left] = matrix[i][right];  // 把右值搬到左 / move right -> left
            matrix[i][right] = tmp;        // 把原左值放到右 / move saved -> right
            left++;                        // 頭指針右移一格 / advance front
            right--;                       // 尾指針左移一格 / retreat back
        }
    }
    // 矩陣已被原地改成旋轉後的樣子，不需回傳值 / matrix mutated in place; no return.
}

Solution — C++

// 演算法 / Algorithm:
// 順時針旋轉 90 度 = 先轉置（沿主對角線鏡射），再把每一列左右翻轉。
// Clockwise 90° rotation = transpose, then reverse each row.
// In-place, O(1) extra space.

class Solution {
public:
    // vector<vector<int>>& 是「對二維向量的參考」，加 & 表示直接改傳入的矩陣，
    // 不複製，符合原地修改的要求。
    // vector<vector<int>>& is a reference to the 2D vector; the & means we
    // mutate the caller's matrix directly (no copy) — exactly what in-place needs.
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();             // size() 回傳列數，即邊長 n / number of rows = n

        // ---- Step 1: 轉置 / transpose ----
        for (int i = 0; i < n; i++) {
            // j 從 i+1 開始，只處理對角線上方，避免重複交換。
            // j from i+1: only above the diagonal, so each pair is swapped once.
            for (int j = i + 1; j < n; j++) {
                // std::swap 直接交換兩個元素的值，不必手動用 tmp。
                // std::swap exchanges two values for us — no manual temporary needed.
                swap(matrix[i][j], matrix[j][i]);
            }
        }

        // ---- Step 2: 每一列左右翻轉 / reverse each row ----
        for (int i = 0; i < n; i++) {
            // reverse(begin, end) 會把區間 [begin, end) 內的元素前後顛倒。
            // matrix[i].begin()/end() 是該列的頭尾迭代器。
            // reverse(begin, end) flips the range [begin, end); begin()/end()
            // are iterators marking the start and one-past-the-end of row i.
            reverse(matrix[i].begin(), matrix[i].end());
        }
        // matrix 已就地旋轉完成 / matrix is rotated in place.
    }
};

複雜度 / Complexity

• Time: O(n²) — 轉置會碰過約一半的格子，翻轉又掃過所有格子，總共與格子數成正比；矩陣有 n × n = n² 個元素，所以是 O(n²)。這裡 n 是矩陣的邊長，不是元素總數。The transpose touches about half the cells and the reversal sweeps all of them; both are proportional to the n² cells. n is the side length, not the element count.
• Space: O(1) — 只用了 tmp、left、right、i、j 等固定數量的變數，沒有隨 n 增長的額外空間，完全原地。Only a fixed number of scalar variables; no extra storage grows with n, so it's truly in-place.

Pitfalls & Edge Cases

• 轉置時內層從 i+1 開始，不能從 0 / Start the inner transpose loop at i+1, not 0. 若從 0 開始，每一對 (i,j) 和 (j,i) 會被換兩次，第二次把它換回原狀，等於沒做轉置。Starting at 0 swaps each pair twice, the second swap undoing the first — the transpose becomes a no-op.
• 順序不能反 / Order matters. 「先轉置再翻列」得到順時針；若反過來「先翻列再轉置」會得到逆時針旋轉，答案就錯了。Transpose-then-reverse gives clockwise; doing it in the opposite order yields a counter-clockwise rotation.
• 不可另開二維矩陣 / Don't allocate a second 2D matrix. 題目硬性規定原地，開新矩陣雖然好寫但不符合要求。The problem explicitly forbids a second grid even though it would be easier.
• n = 1 的邊界 / Single-element matrix. 當 n = 1 時，轉置的內層迴圈（j 從 1 開始已超界）與翻轉（left < right 不成立）都不執行，矩陣保持不變，正是正確答案。For n = 1 both loops do nothing and the matrix stays the same — correctly, since rotating one element changes nothing.
• 負數值不影響 / Negative values are fine. 元素可為 -1000 到 1000，但我們只是搬移、交換數值，從不做加總或乘法，所以沒有溢位風險。We only move values around (no arithmetic), so the negative range and value bounds raise no overflow concerns.