DSA SheetEasy
EditorialPractice

MATRIX › MATRIX TRANSFORMATION AND MODIFICATION

Shift 2D Grid

EasyEditorial · 6 minGenerated by gpt-5.6-luna · Aug 28

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

A row-major matrix represented as one circular sequenceThe figure shows a matrix read row by row as a single sequence. A boundary is placed before the element at index total - k. The elements from that boundary to the end are moved to the front, followed by the earlier elements, and the resulting sequence is placed back into rows of n cells. The picture makes clear that a right shift is a rotation of the row-major sequence, not an independent rotation of each row.ABCDEFGHIJKLABCDEFGHIJKLJKLABCDEFGHIrow-majorreshapeoriginal matrixrow-major sequencecut before Jright shift by k = 3new matrix

Approach

  1. 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.
  2. 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.
  3. Copy grid[i][j] into flat[i * n + j], because this index formula preserves the exact row-major order described by the shifting rule.
  4. 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.
  5. 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.
  6. 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.
  7. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(mn) extraThe 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.

Common mistakestwo wrong index choices that look plausible

Previous · Minimum Operations to Write the Letter Y on a Grid