// 演算法 / 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.
    }
};