Shift 2D Grid — Editorial

Opening the reading…

Intuitionthe row boundary is just the next position in one circular sequence

Read the grid from left to right across each row, then continue at the first cell of the next row. Under the shifting rule, every cell moves to the next position in exactly this order, and the last cell moves back to the first position. So the two-dimensional movement is a one-dimensional circular shift in row-major order.

After one shift, the final element becomes the first element. After k shifts, the last k elements become the prefix and the remaining elements follow them. A complete cycle of m x n shifts changes nothing, so reducing k modulo the total number of cells removes work without changing the answer.

Approach

Read m and n, then compute total = m x n, because row-major indexing needs the row width and the total length of the circular sequence.

Reduce k with k %= total, because every total shifts return every cell to its original position and large k values otherwise cause unnecessary rotation work.

Copy grid[i][j] into flat[i * n + j], because this index formula preserves the exact row-major order described by the shifting rule.

Set start = total - k, because the element that ends up at position 0 is the element that was k positions from the end; starting at total - k rotates right rather than left.

Fill rotated[i] from flat[(start + i) % total], because the modulo wraps the source index back to zero when the copied suffix reaches the end.

Create an m by n answer matrix and write rotated[i * n + j] into answer[i][j], because reshaping the rotated sequence restores the original grid dimensions.

Return the answer, with the k == 0 case returned immediately because no cell changes and the extra arrays are unnecessary.

Complexitythe result is required output, not working memory

MEASURE	BOUND	WHY
Time	O(mn)	The grid is flattened once, the rotated sequence is filled once, and the answer is reshaped once. Each of the mn cells participates in a constant number of assignments, so no cell causes repeated work.
Space	O(mn) extra	The flat, rotated, and answer structures together hold O(mn) values; the returned answer is required output and is excluded from the extra-space bound. The bound is still O(mn) for every valid rectangular shape, including a single row or a single column.

Here m is the number of rows and n is the number of columns; total = m x n is the number of cells.

Annotated solutionC++ · row-major rotation · complete judge-ready implementation

CPPFlatten the grid, rotate the sequence right by k, and reshape it into the answer matrix.

#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int total = m * n;

        k %= total;
        if (k == 0) return grid;

        vector<int> flat(total);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                flat[i * n + j] = grid[i][j];
            }
        }

        int start = total - k;
        vector<int> rotated(total);
        for (int i = 0; i < total; ++i) {
            rotated[i] = flat[(start + i) % total];
        }

        vector<vector<int>> answer(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                answer[i][j] = rotated[i * n + j];
            }
        }

        return answer;
    }
};

The key line is start = total - k. For a right rotation by k, the new first element is the old element k positions before the end. The expression (start + i) % total then walks forward through the old sequence and wraps around exactly once. Keeping rotation and reshaping as separate phases makes the direction visible and avoids mixing two-dimensional coordinates with circular movement.