LeetCode 1914 - Cyclically Rotating a Grid

The problem gives us an m x n matrix called grid, along with an integer k. Both dimensions of the matrix are guaranteed to be even numbers. The task is to rotate every layer of the matrix counter-clockwise exactly k times.

leetcodemediumarraymatrixsimulation

LeetCode Problem 1914

Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation

Solution

LeetCode 1914 - Cyclically Rotating a Grid

Problem Understanding

The problem gives us an m x n matrix called grid, along with an integer k. Both dimensions of the matrix are guaranteed to be even numbers. The task is to rotate every layer of the matrix counter-clockwise exactly k times.

A layer is the rectangular ring formed by the outer boundary of a submatrix. The outermost border is the first layer, the next inner border is the second layer, and so on. Since both dimensions are even, every cell belongs to exactly one layer.

For example, in a 4 x 4 matrix:

1  2  3  4
5  6  7  8
9 10 11 12
13 14 15 16

The outer layer contains:

1 2 3 4 8 12 16 15 14 13 9 5

The inner layer contains:

6 7 11 10

A single counter-clockwise rotation means each element moves one position forward along the layer traversal order.

The output should be the final matrix after every layer has been rotated k times.

The constraints are important:

  • 2 <= m, n <= 50
  • k can be as large as 10^9

The small matrix size means we do not need extremely advanced optimizations, but the very large value of k means we absolutely cannot simulate one rotation at a time.

The key observation is that rotating a layer repeatedly is cyclic. If a layer has length L, then rotating it L times returns it to the original state. Therefore, only k % L effective rotations matter.

Several edge cases are important:

  • Very large k, which requires modular reduction.
  • Small matrices like 2 x 2, where the entire matrix is one layer.
  • Thin inner layers, such as a 2 x N or M x 2 submatrix.
  • Multiple nested layers that must rotate independently.
  • Correct corner handling, since corners belong to both a row and a column traversal if implemented carelessly.

Approaches

Brute Force Approach

A direct simulation would rotate every layer one step at a time, repeating the process k times.

For each rotation:

  1. Traverse the layer boundary.
  2. Move every element one position counter-clockwise.
  3. Repeat for all layers.
  4. Repeat the entire process k times.

This works because it exactly follows the problem statement.

However, it is inefficient because k can be as large as 10^9. Even a small matrix would become impossible to process within time limits if we simulate rotations individually.

Optimal Approach

The better approach treats each layer as a circular array.

The key insight is that every layer can be extracted into a one-dimensional list in traversal order. Once we have this list:

  • Rotating counter-clockwise by k positions is simply a left rotation.
  • We can compute the effective rotation using:

$k \bmod L$

where L is the layer length.

After rotating the extracted list, we place the values back into the matrix following the same traversal order.

This transforms the problem from repeated simulation into direct index manipulation.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k × m × n) O(1) Simulates every rotation individually
Optimal O(m × n) O(m × n) Extracts each layer, rotates once using modular arithmetic

Algorithm Walkthrough

  1. Determine the number of layers.

The number of layers is:

$\min(m,n)/2$

because every layer consumes one row and one column from each side. 2. Process each layer independently.

For a layer indexed by layer:

  • Top row index is layer
  • Bottom row index is m - 1 - layer
  • Left column index is layer
  • Right column index is n - 1 - layer
  1. Extract the layer elements.

Traverse the boundary in a consistent order:

  • Top row, left to right
  • Right column, top to bottom
  • Bottom row, right to left
  • Left column, bottom to top

Store all values in a list called elements. 4. Compute effective rotations.

If the layer length is L, then rotating by k is equivalent to rotating by:

$k \bmod L$

because the sequence repeats after one full cycle. 5. Rotate the extracted array.

Since the movement is counter-clockwise, the extracted traversal order corresponds to a left rotation.

We can build the rotated array as:

rotated = elements[shift:] + elements[:shift]
  1. Write the rotated values back.

Traverse the same boundary positions again in exactly the same order, replacing matrix values with the rotated sequence. 7. Continue for all layers.

Since every cell belongs to exactly one layer, the final matrix is fully updated after processing all layers.

Why it works

Each layer forms a closed cycle. Extracting the layer converts the problem into rotating a circular array. Since the traversal order matches the physical movement around the layer boundary, performing a left rotation on the extracted array exactly matches the required counter-clockwise matrix rotation. Writing the rotated values back into the same positions reconstructs the correct final grid.

Python Solution

from typing import List

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        rows = len(grid)
        cols = len(grid[0])

        layers = min(rows, cols) // 2

        for layer in range(layers):
            top = layer
            bottom = rows - 1 - layer
            left = layer
            right = cols - 1 - layer

            elements = []

            # Top row
            for col in range(left, right + 1):
                elements.append(grid[top][col])

            # Right column
            for row in range(top + 1, bottom):
                elements.append(grid[row][right])

            # Bottom row
            for col in range(right, left - 1, -1):
                elements.append(grid[bottom][col])

            # Left column
            for row in range(bottom - 1, top, -1):
                elements.append(grid[row][left])

            length = len(elements)
            shift = k % length

            rotated = elements[shift:] + elements[:shift]

            index = 0

            # Top row
            for col in range(left, right + 1):
                grid[top][col] = rotated[index]
                index += 1

            # Right column
            for row in range(top + 1, bottom):
                grid[row][right] = rotated[index]
                index += 1

            # Bottom row
            for col in range(right, left - 1, -1):
                grid[bottom][col] = rotated[index]
                index += 1

            # Left column
            for row in range(bottom - 1, top, -1):
                grid[row][left] = rotated[index]
                index += 1

        return grid

The implementation begins by computing the number of layers in the matrix. Each layer is processed independently.

For every layer, the code calculates the four boundaries: top, bottom, left, and right. These boundaries define the rectangular ring currently being rotated.

The next section extracts all layer elements into a one-dimensional list. The traversal order is extremely important because the same order must later be used when writing values back into the grid.

Once the elements are collected, the code computes the effective number of rotations using modulo arithmetic. This avoids unnecessary repeated rotations when k is very large.

The rotated array is created using Python slicing. A left rotation corresponds exactly to the required counter-clockwise movement.

Finally, the code traverses the same boundary positions again and writes the rotated values back into the matrix.

Because every layer is processed separately and every cell belongs to exactly one layer, the entire matrix is correctly transformed.

Go Solution

func rotateGrid(grid [][]int, k int) [][]int {
	rows := len(grid)
	cols := len(grid[0])

	layers := min(rows, cols) / 2

	for layer := 0; layer < layers; layer++ {
		top := layer
		bottom := rows - 1 - layer
		left := layer
		right := cols - 1 - layer

		elements := []int{}

		// Top row
		for col := left; col <= right; col++ {
			elements = append(elements, grid[top][col])
		}

		// Right column
		for row := top + 1; row < bottom; row++ {
			elements = append(elements, grid[row][right])
		}

		// Bottom row
		for col := right; col >= left; col-- {
			elements = append(elements, grid[bottom][col])
		}

		// Left column
		for row := bottom - 1; row > top; row-- {
			elements = append(elements, grid[row][left])
		}

		length := len(elements)
		shift := k % length

		rotated := append(elements[shift:], elements[:shift]...)

		index := 0

		// Top row
		for col := left; col <= right; col++ {
			grid[top][col] = rotated[index]
			index++
		}

		// Right column
		for row := top + 1; row < bottom; row++ {
			grid[row][right] = rotated[index]
			index++
		}

		// Bottom row
		for col := right; col >= left; col-- {
			grid[bottom][col] = rotated[index]
			index++
		}

		// Left column
		for row := bottom - 1; row > top; row-- {
			grid[row][left] = rotated[index]
			index++
		}
	}

	return grid
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation follows the same algorithmic structure as the Python version. The main difference is slice handling.

In Python, list slicing naturally creates rotated arrays. In Go, the rotated sequence is constructed using append(elements[shift:], elements[:shift]...).

Go also requires an explicit helper function for min, since there is no built-in integer minimum function in the standard language.

Since all constraints are small, integer overflow is not a concern in this problem.

Worked Examples

Example 1

Input:

grid = [
  [40,10],
  [30,20]
]
k = 1

There is only one layer.

Step 1: Extract layer

Traversal order:

Position Value
(0,0) 40
(0,1) 10
(1,1) 20
(1,0) 30

Extracted array:

[40, 10, 20, 30]

Step 2: Rotate left by 1

[10, 20, 30, 40]

Step 3: Write back

Position New Value
(0,0) 10
(0,1) 20
(1,1) 30
(1,0) 40

Final matrix:

[
  [10,20],
  [40,30]
]

Example 2

Input:

grid = [
  [1,2,3,4],
  [5,6,7,8],
  [9,10,11,12],
  [13,14,15,16]
]
k = 2

There are two layers.

Outer Layer Extraction

Traversal order:

[1,2,3,4,8,12,16,15,14,13,9,5]

Length is 12.

Effective shift:

2 % 12 = 2

Rotated:

[3,4,8,12,16,15,14,13,9,5,1,2]

Outer Layer After Writing Back

3  4  8 12
2  .  . 16
1  .  . 15
5  9 13 14

Inner Layer Extraction

Traversal order:

[6,7,11,10]

Effective shift:

2 % 4 = 2

Rotated:

[11,10,6,7]

Final Matrix

[
  [3,4,8,12],
  [2,11,10,16],
  [1,7,6,15],
  [5,9,13,14]
]

Complexity Analysis

Measure Complexity Explanation
Time O(m × n) Every matrix cell is extracted and written exactly once
Space O(m × n) Layer arrays collectively store all matrix elements

The algorithm processes each layer independently, but every cell belongs to exactly one layer. Across all layers, the total number of extracted elements equals the number of cells in the matrix.

The auxiliary storage used for temporary layer arrays also sums to at most the total number of matrix elements.

Test Cases

from typing import List

class Solution:
    def rotateGrid(self, grid: List[List[int]], k: int) -> List[List[int]]:
        rows = len(grid)
        cols = len(grid[0])

        layers = min(rows, cols) // 2

        for layer in range(layers):
            top = layer
            bottom = rows - 1 - layer
            left = layer
            right = cols - 1 - layer

            elements = []

            for col in range(left, right + 1):
                elements.append(grid[top][col])

            for row in range(top + 1, bottom):
                elements.append(grid[row][right])

            for col in range(right, left - 1, -1):
                elements.append(grid[bottom][col])

            for row in range(bottom - 1, top, -1):
                elements.append(grid[row][left])

            shift = k % len(elements)
            rotated = elements[shift:] + elements[:shift]

            index = 0

            for col in range(left, right + 1):
                grid[top][col] = rotated[index]
                index += 1

            for row in range(top + 1, bottom):
                grid[row][right] = rotated[index]
                index += 1

            for col in range(right, left - 1, -1):
                grid[bottom][col] = rotated[index]
                index += 1

            for row in range(bottom - 1, top, -1):
                grid[row][left] = rotated[index]
                index += 1

        return grid

solver = Solution()

# Example 1
assert solver.rotateGrid([[40,10],[30,20]], 1) == [
    [10,20],
    [40,30]
]

# Example 2
assert solver.rotateGrid(
    [
        [1,2,3,4],
        [5,6,7,8],
        [9,10,11,12],
        [13,14,15,16]
    ],
    2
) == [
    [3,4,8,12],
    [2,11,10,16],
    [1,7,6,15],
    [5,9,13,14]
]

# Large k equivalent to zero rotations
assert solver.rotateGrid([[1,2],[3,4]], 4) == [
    [1,2],
    [3,4]
]

# Rectangular matrix
assert solver.rotateGrid(
    [
        [1,2,3,4],
        [5,6,7,8]
    ],
    1
) == [
    [2,3,4,8],
    [1,5,6,7]
]

# Multiple layers with large k
assert solver.rotateGrid(
    [
        [1,2,3,4,5,6],
        [7,8,9,10,11,12],
        [13,14,15,16,17,18],
        [19,20,21,22,23,24]
    ],
    100
) == [
    [13,7,1,2,3,4],
    [19,9,10,11,17,5],
    [20,8,14,15,23,6],
    [21,22,23,24,18,12]
]

# Minimal matrix
assert solver.rotateGrid([[1,2],[3,4]], 1) == [
    [2,4],
    [1,3]
]

Test Summary

Test Why
[[40,10],[30,20]], k=1 Validates smallest non-trivial matrix
4x4 example Validates multiple layers
k equals layer length Ensures modulo reduction works
2x4 matrix Validates rectangular traversal
large k Confirms efficient cyclic rotation
minimal matrix Tests corner-only layer handling

Edge Cases

Very Large k

The value of k can be as large as 10^9. A naive implementation that performs one rotation at a time would be far too slow.

The implementation handles this correctly by computing:

$k \bmod L$

where L is the number of elements in the current layer. Since rotations are cyclic, this produces the same final result while avoiding unnecessary work.

Smallest Possible Matrix

A 2 x 2 matrix contains exactly one layer consisting only of the four corner elements. This case can easily produce duplicate corner processing bugs.

The traversal logic avoids duplicates because:

  • Top and bottom rows include corners.
  • Left and right columns exclude already-visited corners.

This guarantees every cell is visited exactly once.

Rectangular Matrices

The matrix is not necessarily square. Cases like 2 x 6 or 6 x 2 can break implementations that assume symmetric dimensions.

The algorithm avoids this issue by computing boundaries independently for rows and columns. Every traversal loop uses explicit top, bottom, left, and right indices, so the same logic works for both square and rectangular grids.

Multiple Nested Layers

Matrices can contain several independent layers. A common mistake is accidentally mixing values between layers.

This implementation processes each layer separately:

  • Extract current layer
  • Rotate current layer
  • Write current layer back

No values from one layer can interfere with another, guaranteeing correctness for deeply nested matrices.