1260. Shift 2D Grid

題目 / Problem

中文： 給定一個 m x n 的二維陣列 grid 和一個整數 k。你需要把 grid 平移 k 次。

每一次平移操作： - grid[i][j] 的元素移動到 grid[i][j + 1]（往右一格）。 - grid[i][n - 1]（每列最後一格）的元素移動到 grid[i + 1][0]（下一列的開頭）。 - grid[m - 1][n - 1]（右下角最後一格）的元素移動到 grid[0][0]（繞回左上角）。

回傳平移 k 次之後的二維陣列。

English: Given an m x n 2D grid and an integer k, shift the grid k times. In one shift, every element moves one cell to the right; the last cell of a row wraps to the start of the next row; and the bottom-right cell wraps all the way back to the top-left. Return the grid after k shifts.

Constraints / 限制： - m == grid.length, n == grid[i].length - 1 <= m, n <= 50 - -1000 <= grid[i][j] <= 1000 - 0 <= k <= 100

Worked example / 範例：

Input:  grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
Output: [[9,1,2],[3,4,5],[6,7,8]]

把整個網格想成一條線 1 2 3 4 5 6 7 8 9，往右移 1 格並繞回，得到 9 1 2 3 4 5 6 7 8，再折回 3x3 就是答案。

名詞解釋 / Glossary

• 二維陣列 / 2D grid：一個「表格」，用兩個索引 grid[i][j] 取值，i 是列（row，第幾橫排），j 是行（column，第幾直排）。
• 攤平 / flatten：把二維表格按「一列接一列」的順序，攤成一條一維的直線。座標 (i, j) 對應到一維索引 i * n + j。
• 取餘數 / modulo (%)：a % b 是 a 除以 b 的餘數。這裡用來做「繞回」——超過總長度就從頭算起。
• 循環位移 / cyclic shift：把一串資料整體往一個方向移動，掉出邊界的元素從另一端補回來，像一個圈。
• malloc / free（C）：malloc 向系統要一塊記憶體來存資料，用完要用 free 還回去；LeetCode 的 C 題需要你自己配置回傳陣列的記憶體。
• 指標 / pointer（C）：一個存「記憶體位址」的變數。int** 代表「指向一堆 int* 的指標」，也就是二維陣列的表示方式。
• vector（C++）：C++ 標準函式庫的「會自動長大的陣列」，不必手動管理記憶體，用 .size() 取長度、用 [] 取值。

思路

最直覺的暴力法就是照著題目描述模擬：做 k 次，每次把每個元素往右挪一格、處理邊界繞回。這樣做是對的，但每一次平移都要走遍整個網格 m*n 個元素，總共要 k * m * n 次操作。雖然本題資料量小（m, n <= 50, k <= 100）跑得動，但其實有更漂亮、更快的做法。關鍵觀察是：不管每一格具體怎麼移動，整個網格「按列攤平」之後其實就是一條直線，而一次平移，就等於這條直線整體往右循環移動一格。所以平移 k 次，就是把這條長度 total = m*n 的直線往右循環移動 k 格。又因為移動 total 格會回到原狀，所以真正有效的移動量是 k % total。對攤平後索引為 idx 的元素，它平移後的新位置就是 (idx + k) % total。我們只要一次掃過所有元素，把每個 grid[i][j]（其攤平索引是 i*n + j）直接放到新網格的 (i*n + j + k) % total 位置，再把那個一維索引折回 (row, col) 即可。這樣只需一次遍歷，O(m*n) 完成，不必真的模擬 k 次。

The brute-force idea is to literally simulate: repeat k times, and in each pass push every element one cell to the right, wrapping at the borders. That's correct but costs k * m * n operations. The cleaner insight is that shifting the grid once is exactly a single right cyclic shift of the grid flattened row by row into one long line of length total = m*n. Shifting k times just rotates that line right by k, and rotating by a full total returns to the start, so the effective amount is k % total. An element whose flattened index is idx lands at (idx + k) % total. So we walk every cell once, compute the flattened index i*n + j, add k, take it modulo total, and unfold that new 1D index back into (row, col) in the answer grid. One pass, O(m*n), no repeated simulation.

逐步走查 / Walkthrough

用範例 grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1。這裡 m = 3, n = 3, total = 9, 有效位移 k % 9 = 1。

攤平順序（idx = i*3 + j）：idx 0→1, 1→2, 2→3, 3→4, 4→5, 5→6, 6→7, 7→8, 8→9。

每個元素的新一維位置 = (idx + 1) % 9，再折回 newRow = pos / 3, newCol = pos % 3：

把每個值填到新網格對應位置，得到：

row0: [9, 1, 2]
row1: [3, 4, 5]
row2: [6, 7, 8]

正是預期輸出。注意只有 9（在 idx 8）發生了繞回：(8+1)%9 = 0，跑回左上角 (0,0)。

Solution — C

// 演算法：把二維網格按列攤平成一條長度 total=m*n 的直線，
// 一次平移 = 這條線向右循環一格；平移 k 次 = 每個元素移到 (idx+k)%total。
// Algorithm: flatten row-major; one shift = right cyclic shift by 1,
// so k shifts send flattened index idx to (idx + k) % total. One pass, O(m*n).

int** shiftGrid(int** grid, int gridSize, int* gridColSize, int k,
                int* returnSize, int** returnColumnSizes) {
    int m = gridSize;              // m 是列數（幾橫排）/ m = number of rows
    int n = gridColSize[0];        // n 是行數（每列幾格）/ n = columns per row
    int total = m * n;             // total 是元素總數 / total number of cells
    k = k % total;                 // 移動 total 格會回到原狀，只留有效位移 / effective shift only

    // 配置回傳用的二維陣列：先要 m 個 int* 的陣列（每個指向一列）
    // Allocate the answer: an array of m row-pointers (int*)
    int** ans = (int**)malloc(sizeof(int*) * m);
    // returnColumnSizes 要回傳每一列的長度，也需要 m 個 int 的陣列
    // returnColumnSizes reports each row's length; needs m ints
    *returnColumnSizes = (int*)malloc(sizeof(int) * m);

    for (int i = 0; i < m; i++) {          // 逐列配置與設定長度 / set up each row
        ans[i] = (int*)malloc(sizeof(int) * n);  // 每列 n 個 int / n ints per row
        (*returnColumnSizes)[i] = n;             // 告訴 LeetCode 這列有 n 格 / this row has n cols
    }
    *returnSize = m;               // 回傳的網格有 m 列 / the returned grid has m rows

    // 掃過每一個元素，直接算出它的新位置並填入 / place each cell at its shifted spot
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int idx = i * n + j;           // 攤平後的舊一維索引 / old flattened index
            int pos = (idx + k) % total;   // 循環移動後的新一維索引 / new index after rotation
            int newRow = pos / n;          // 折回列座標：整除得列 / unfold row = pos / n
            int newCol = pos % n;          // 折回行座標：取餘得行 / unfold col = pos % n
            ans[newRow][newCol] = grid[i][j];  // 把值搬到新位置 / copy value to its new cell
        }
    }
    return ans;                    // 回傳新網格 / return the new grid
}

Solution — C++

// 演算法（同 C）：按列攤平，平移 k 次 = 每個元素從一維索引 idx 移到 (idx+k)%total。
// Algorithm: flatten row-major; k shifts move flattened index idx to (idx + k) % total.
// One pass over all cells, O(m*n) time.

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();          // m 是列數 / number of rows (vector 的元素個數)
        int n = grid[0].size();       // n 是每列行數 / columns per row
        int total = m * n;            // 元素總數 / total number of cells
        k = k % total;                // 只保留有效位移 / keep only the effective shift

        // 建立一個 m x n、全部初始化為 0 的答案網格
        // Make an m x n answer grid, every cell initialized to 0
        // vector<vector<int>> 是「陣列的陣列」，第二個參數給每列的初始內容
        vector<vector<int>> ans(m, vector<int>(n, 0));

        for (int i = 0; i < m; i++) {         // 逐列 / for each row
            for (int j = 0; j < n; j++) {     // 逐格 / for each cell
                int idx = i * n + j;          // 舊的攤平索引 / old flattened index
                int pos = (idx + k) % total;  // 移動後的新索引 / rotated new index
                // pos / n 得到新列、pos % n 得到新行，把值放進去
                // pos / n gives new row, pos % n gives new column; store the value
                ans[pos / n][pos % n] = grid[i][j];
            }
        }
        return ans;                   // 回傳結果，vector 會自動管理記憶體 / vectors free themselves
    }
};

複雜度 / Complexity

• Time: O(m·n) — 我們只掃過網格一次，每個元素做常數次算術（加法、取餘、除法）就決定新位置。相較暴力模擬的 O(k·m·n)，這裡與 k 無關，因為我們用 k % total 一步到位。m·n 是元素總數。 We visit each of the m·n cells exactly once, doing O(1) arithmetic per cell. Independent of k because k % total collapses all shifts into one computation.
• Space: O(m·n) — 需要一個同樣大小的新網格來存放結果（不含回傳值本身則為 O(1) 額外空間）。攤平只是「概念上」的，程式並沒有真的另外建一條一維陣列。 We allocate one new grid of the same size for the output. The flattening is conceptual — no separate 1D array is materialized, so no extra space beyond the answer.

Pitfalls & Edge Cases

• 忘記取 k % total / Forgetting k % total：k 可能大到讓元素繞好幾圈；若不取餘數，索引 (idx + k) 會超出陣列範圍造成越界。取餘後保證新索引落在 [0, total)。When k >= total, raw idx + k overflows the bounds; the modulo keeps it valid.
• 列數與行數搞混 / Mixing up m and n：攤平用 i*n + j（乘的是「每列寬度」n，不是 m），折回用 pos / n 與 pos % n。用錯會讓非方陣（m != n）的答案整個錯位。Always multiply/divide by n (row width), not m.
• 就地修改會覆蓋資料 / In-place overwrite corrupts data：若直接在原 grid 上搬移，還沒讀到的元素可能已被覆蓋。用一個獨立的新網格 ans 就避開這個陷阱。Writing into the source grid can clobber cells you haven't read yet — a fresh output grid avoids it.
• C 的記憶體配置 / C allocation details：必須同時配置 ans、每一列 ans[i]，還有 *returnColumnSizes 並填入每列長度 n，且設定 *returnSize = m；漏掉任何一個 LeetCode 會判錯或崩潰。You must set returnSize, allocate returnColumnSizes, and fill each row length.
• k = 0 的情況 / When k = 0：0 % total = 0，每個元素 (idx + 0) % total = idx 留在原位，程式自然回傳原網格的複製，無需特判。The formula already handles it — no special case needed.