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