Abstract / Summary

Rotate a grid by moving each element to the next position in a cycle according to specified shift directions.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 74% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Matrix
• Simulation

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation rotates the elements of a rectangular matrix by moving each element along its concentric “ring”. The rotation distance k is applied uniformly to every ring, preserving the shape of the matrix while shifting values clockwise (or counter-clockwise depending on the sign of k). The algorithm proceeds in three conceptual phases: marking visited cells, collecting coordinates for each ring, and writing the rotated values into a newly allocated result grid.

Key Steps

The first phase creates a boolean matrix done that mirrors the dimensions of the input grid. This matrix records whether a cell has already been assigned to a ring, preventing revisits during the traversal.

height = len(grid)
width  = len(grid[0])

done = []
for y in range(height):
    done.append([ False ] * width)

Next, the algorithm walks the grid in a spiral pattern using a direction vector list deltas. The variables x, y, and direction track the current position and movement direction. The level variable identifies the current ring index, starting at 1. As long as the current cell has not been visited, its coordinates are appended to the list for the current ring in the rings dictionary, and the cell is marked as visited.

rings  = defaultdict(list)
deltas = [ [ +1, 0 ], [ 0, +1 ], [ -1, 0 ], [ 0, -1 ] ]
x = y = direction = 0
dx, dy = deltas[direction]
level  = 1
while not done[y][x]:
    rings[level].append(( x, y ))
    done[y][x] = True
    x += dx
    y += dy
    if x < 0 or y < 0 or x == width or y == height or done[y][x]:
        x -= dx
        y -= dy
        direction += 1
        if direction == len(deltas):
            direction = 0
            level    += 1
        dx, dy = deltas[direction]
        x += dx
        y += dy

After the traversal completes, a result matrix of the same size is allocated, initially filled with None. This matrix will receive the rotated values.

result = []
for y in range(height):
    result.append([ None ] * width)

The final phase iterates over each ring stored in rings. For each position one in a ring, the target position after rotation is computed as (one + k) % size, where size is the number of cells in the ring. The value from the source coordinate gx, gy is placed into the destination coordinate x, y of the result matrix.

for r in rings:
    size = len(rings[r])
    for one in range(size):
        two = (one + k) % size
        x,  y  = rings[r][one]
        gx, gy = rings[r][two]
        result[y][x] = grid[gy][gx]

The function returns the fully populated result matrix, which reflects the original grid after the specified rotation.

Edge Cases Handled

The traversal logic includes boundary checks (x < 0 or y < 0 or x == width or y == height) that automatically stop movement when the next step would leave the matrix. The additional condition done[y][x] ensures that the algorithm correctly transitions to the next inner ring once the outer perimeter is exhausted. Because the while loop continues until the current cell is already marked, the code gracefully handles grids where the height and width differ, as well as degenerate cases such as a single row or a single column. In those scenarios, the direction changes occur precisely when the next step would either cross the border or revisit a cell, resulting in a correct ring decomposition even when a ring consists of a line rather than a closed loop.

The modulo operation (one + k) % size guarantees that any integer k, positive or negative, maps to a valid index within the ring. This prevents out-of-range accesses and naturally wraps the rotation around the ring regardless of the magnitude of k.

Performance Optimizations

The algorithm avoids repeated allocation of intermediate structures by constructing the done matrix once and reusing it throughout the traversal. The use of a defaultdict(list) for rings eliminates the need for explicit existence checks when appending coordinates, streamlining the ring collection step.

By pre-allocating the result matrix with a single pass over the rows, the code ensures that each assignment in the final phase writes directly to its final location without additional copying. The inner loop that copies values from the source grid to the result grid accesses each cell exactly once, resulting in a linear pass over the total number of elements.

Direction changes are performed only when necessary-specifically when the next coordinate would be out of bounds or already visited-so the traversal proceeds with minimal branching. The incremental update of x and y using dx and dy keeps arithmetic simple and cache-friendly, contributing to efficient execution even for large matrices.

Imagine a big square box filled with toys arranged in layers, like a set of nested boxes sitting inside one another. The goal is to take all the toys on the outermost layer and shift them over by a certain number of spaces, and then do the same thing for the layer inside that one, and repeat until every layer has been moved.

First, the code builds a map to keep track of which toys belong to which layer. It walks along the edge of the box, picking up the position of every toy until it finishes a full loop, and then it moves to the next inner layer to do it again. It keeps a helpful list that says exactly which toys are in which layer so nothing gets lost.

Once the layers are mapped out, the code brings out a fresh, empty box. It looks at a specific layer, counts how many spots it needs to slide the toys, and picks up a toy from one spot in the old box and sets it into its new home in the fresh box. It does this for every single toy in every single layer. By the time it finishes moving all the toys to their new spots, the new box is completely filled and every toy has been shifted exactly the right amount.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java				TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go	Rust	TS
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality