Cyclically Rotating a Grid — Editorial

Opening the reading…

Intuitionwhy every layer can be solved independently

A rotation never moves an element from one layer to another. The outer ring stays the outer ring, the next ring stays the next ring, and so on. That lets you ignore the full matrix temporarily and describe one layer as a one-dimensional circular sequence of its boundary cells.

Read a layer clockwise, starting at its top-left corner. After one counter-clockwise rotation, the value that was later in this clockwise sequence moves into each earlier position, so the sequence becomes a left shift by one. Applying k rotations is therefore a left shift by k modulo the layer length. Extracting and writing the layer in the same order keeps the direction consistent.

One layer rotation becomes a left shift when the boundary is read clockwise.

Approachextract, shift, and write each ring

Compute the number of layers as min(m, n) / 2, because each layer consumes one row and one column from every side and the problem guarantees even dimensions.

Process layer l from the outside inward, because each layer has its own cycle and changing one ring cannot affect the positions belonging to another.

Append the top edge from left to right, the right edge from top to bottom, the bottom edge from right to left, and the left edge from bottom to top. The corner ranges deliberately avoid duplicates, because each corner already belongs to the preceding edge.

Set shift to k modulo the layer length, because shifting by a complete circumference returns every value to its original position and k can be much larger than the grid.

Build the rotated sequence with rotated[i] = values[(i + shift) % length]. This takes the value that appears shift positions later in clockwise order, which is exactly a counter-clockwise shift.

Write the rotated sequence back using the same four edge traversals used for extraction. Reusing the order makes every sequence position map back to the correct cell instead of reversing the rotation direction.

Return the modified grid after all layers have been processed, because every cell belongs to exactly one layer and has then received its final value.

Complexityeach cell is handled a constant number of times

MEASURE	BOUND	WHY
Time	O(mn)	Across all layers, every cell is extracted once and written once. The layer boundaries are disjoint, so the total number of sequence operations is exactly proportional to the number of grid cells.
Space	O(m + n) extra	The returned grid is required output and is excluded from the space bound. For one layer, values and rotated together use space proportional to its perimeter; the outermost layer has at most 2m + 2n cells, so the worst extra space is O(m + n).

Here m is the number of rows and n is the number of columns. The grid has mn cells.

Annotated solutionC++ · sequence-based simulation · the clear version to remember

CPPExtract each layer clockwise, left-shift its sequence, and write it back through the same four edges.

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int layers = min(m, n) / 2;

        for (int layer = 0; layer < layers; ++layer) {
            vector<int> values;

            for (int col = layer; col < n - layer; ++col) {
                values.push_back(grid[layer][col]);
            }
            for (int row = layer + 1; row < m - layer; ++row) {
                values.push_back(grid[row][n - 1 - layer]);
            }
            for (int col = n - 2 - layer; col >= layer; --col) {
                values.push_back(grid[m - 1 - layer][col]);
            }
            for (int row = m - 2 - layer; row > layer; --row) {
                values.push_back(grid[row][layer]);
            }

            int length = values.size();
            int shift = k % length;
            vector<int> rotated(length);

            for (int i = 0; i < length; ++i) {
                rotated[i] = values[(i + shift) % length];
            }

            int index = 0;
            for (int col = layer; col < n - layer; ++col) {
                grid[layer][col] = rotated[index++];
            }
            for (int row = layer + 1; row < m - layer; ++row) {
                grid[row][n - 1 - layer] = rotated[index++];
            }
            for (int col = n - 2 - layer; col >= layer; --col) {
                grid[m - 1 - layer][col] = rotated[index++];
            }
            for (int row = m - 2 - layer; row > layer; --row) {
                grid[row][layer] = rotated[index++];
            }
        }

        return grid;
    }
};

The extraction and assignment loops look repetitive, but their ranges carry the correctness proof. The top edge includes both top corners, the right edge skips its top corner, the bottom edge skips the right corner, and the left edge skips both corners already seen. The same ranges are used in both directions, so the sequence length and the number of assigned cells must match.

The in-place alternativeconstant extra space, but more indexing

You can avoid the temporary vectors by moving values around each layer in cycles. A position in the clockwise sequence sends its old value to the position shift places earlier, and positions split into gcd(length, shift) independent cycles. This is an optimization for memory, not time: it keeps O(mn) time and reduces working storage to O(1), but the coordinate mapping is harder to audit.

CPPAn O(1)-extra-space cycle rotation using a clockwise index-to-cell mapping.

#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int m = grid.size();
        int n = grid[0].size();
        int layers = min(m, n) / 2;

        auto getCell = [&](int layer, int index) -> int& {
            int height = m - 2 * layer;
            int width = n - 2 * layer;

            if (index < width) {
                return grid[layer][layer + index];
            }
            index -= width;
            if (index < height - 1) {
                return grid[layer + 1 + index][n - 1 - layer];
            }
            index -= height - 1;
            if (index < width - 1) {
                return grid[m - 1 - layer][n - 2 - layer - index];
            }
            index -= width - 1;
            return grid[m - 2 - layer - index][layer];
        };

        for (int layer = 0; layer < layers; ++layer) {
            int length = 2 * (m - 2 * layer) + 2 * (n - 2 * layer) - 4;
            int shift = k % length;
            if (shift == 0) {
                continue;
            }

            int cycles = gcd(length, shift);
            for (int start = 0; start < cycles; ++start) {
                int current = start;
                int carry = getCell(layer, current);

                while (true) {
                    int next = (current - shift + length) % length;
                    swap(carry, getCell(layer, next));
                    current = next;
                    if (current == start) {
                        break;
                    }
                }
            }
        }

        return grid;
    }
};