// 演算法 / Algorithm:
// 用 top/bottom/left/right 四條邊界框住未讀區域，每圈依序讀 上排→右行→下排→左行，
// 讀完一條就把該邊界往內收一格，直到邊界交錯為止。
// Frame the unread region with four boundaries; each ring reads top→right→bottom→left,
// shrinking the matching boundary after every pass, until the boundaries cross.

#include <stdlib.h>  // malloc 在這裡宣告 / malloc is declared here

/* LeetCode 給的簽名：matrix 是 int**，matrixSize 是列數 m，
 * matrixColSize[i] 是第 i 列的行數 n，returnSize 要寫回結果長度。
 * LeetCode signature: matrix is int**, matrixSize = m,
 * matrixColSize[i] = n for row i, write the result length into *returnSize. */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    int m = matrixSize;             // 列數 / number of rows
    int n = matrixColSize[0];       // 行數（每列等長）/ number of columns (all rows equal)

    int total = m * n;              // 元素總數 / total number of elements
    *returnSize = total;            // 透過指標把長度回傳給呼叫者 / report length to caller via pointer

    // 向系統要一塊能裝 total 個 int 的記憶體；回傳的指標就是輸出陣列
    // Ask the OS for room for `total` ints; the returned pointer is our output array
    int* out = (int*)malloc(sizeof(int) * total);

    int k = 0;                      // out 的下一個寫入位置 / next write slot in out

    int top = 0, bottom = m - 1;    // 上下邊界（含端點）/ top & bottom row boundaries (inclusive)
    int left = 0, right = n - 1;    // 左右邊界（含端點）/ left & right column boundaries (inclusive)

    // 只要還有未讀的格子就繼續 / keep going while an unread rectangle still exists
    while (top <= bottom && left <= right) {

        // (1) 沿 top 這一列，由左到右 / top row, left → right
        for (int j = left; j <= right; j++)
            out[k++] = matrix[top][j];   // matrix[top][j] 取第 top 列第 j 行 / cell at row top, col j
        top++;                            // 這一列讀完，邊界下移 / done with this row, move boundary down

        // (2) 沿 right 這一行，由上到下 / right column, top → bottom
        for (int i = top; i <= bottom; i++)
            out[k++] = matrix[i][right];
        right--;                          // 最右行讀完，邊界左移 / done, move boundary left

        // (3) 沿 bottom 這一列，由右到左；先確認還有列可讀，避免單列重讀
        //     bottom row, right → left; guard against re-reading a single leftover row
        if (top <= bottom) {
            for (int j = right; j >= left; j--)
                out[k++] = matrix[bottom][j];
            bottom--;                     // 最底列讀完，邊界上移 / move boundary up
        }

        // (4) 沿 left 這一行，由下到上；先確認還有行可讀，避免單行重讀
        //     left column, bottom → top; guard against re-reading a single leftover column
        if (left <= right) {
            for (int i = bottom; i >= top; i--)
                out[k++] = matrix[i][left];
            left++;                       // 最左行讀完，邊界右移 / move boundary right
        }
    }

    return out;   // 回傳結果陣列；LeetCode 會負責 free / return result; LeetCode frees it
}