1914. Cyclically Rotating a Grid

Array
Matrix
Simulation

TIME

O(m × n)

SPACE

O(m + n)

Intuition

Each layer is an independent cycle. If we list a layer's cells around the border, one rotation moves each value into the adjacent cell in the counter-clockwise direction. With the coordinate order used below, the value written at position i should come from position (i - k) % length.

Because k can be large, reduce it by the layer length.

Approach

Process each layer from outside to inside.
Collect the layer coordinates in counter-clockwise order:
- down the left column
- right along the bottom row
- up the right column
- left along the top row
Store the values at those coordinates.
For each coordinate index i, write values[(i - k) % length] back to that coordinate.

Complexity

Time: O(m × n), every cell belongs to exactly one layer
Space: O(m + n), temporary storage for one layer at a time

Edge Cases

2 x 2 grid -> one layer with four cells
Large k -> use modulo per layer
Rectangular grids -> layer boundaries handle unequal dimensions

Code

from typing import List


class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        """
        1914. Cyclically Rotating a Grid
        Time: O(m × n)
        Space: O(m + n)
        """
        m, n = len(grid), len(grid[0])
        layers = min(m, n) // 2

        for layer in range(layers):
            coords = self._layer_coordinates(m, n, layer)
            values = [grid[row][col] for row, col in coords]
            shift = k % len(values)

            for i, (row, col) in enumerate(coords):
                grid[row][col] = values[(i - shift) % len(values)]

        return grid

    def _layer_coordinates(self, m: int, n: int, layer: int) -> List[tuple[int, int]]:
        top = layer
        bottom = m - 1 - layer
        left = layer
        right = n - 1 - layer
        coords = []

        for row in range(top, bottom + 1):
            coords.append((row, left))

        for col in range(left + 1, right + 1):
            coords.append((bottom, col))

        for row in range(bottom - 1, top - 1, -1):
            coords.append((row, right))

        for col in range(right - 1, left, -1):
            coords.append((top, col))

        return coords

import java.util.*;

/**
 * 1914. Cyclically Rotating a Grid
 * Time: O(m × n)
 * Space: O(m + n)
 */
class Solution {
    public int[][] rotateGrid(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        int layers = Math.min(m, n) / 2;

        for (int layer = 0; layer < layers; layer++) {
            List<int[]> coords = layerCoordinates(m, n, layer);
            int size = coords.size();
            int[] values = new int[size];

            for (int i = 0; i < size; i++) {
                int[] cell = coords.get(i);
                values[i] = grid[cell[0]][cell[1]];
            }

            int shift = k % size;

            for (int i = 0; i < size; i++) {
                int[] cell = coords.get(i);
                grid[cell[0]][cell[1]] = values[(i - shift + size) % size];
            }
        }

        return grid;
    }

    private List<int[]> layerCoordinates(int m, int n, int layer) {
        int top = layer;
        int bottom = m - 1 - layer;
        int left = layer;
        int right = n - 1 - layer;
        List<int[]> coords = new ArrayList<>();

        for (int row = top; row <= bottom; row++) {
            coords.add(new int[]{row, left});
        }

        for (int col = left + 1; col <= right; col++) {
            coords.add(new int[]{bottom, col});
        }

        for (int row = bottom - 1; row >= top; row--) {
            coords.add(new int[]{row, right});
        }

        for (int col = right - 1; col > left; col--) {
            coords.add(new int[]{top, col});
        }

        return coords;
    }
}