Rotate a Matrix 90°

Rotating a matrix by 90° turns the whole grid a quarter turn, the way you would turn a photo. Clockwise, the top row swings round to become the rightmost column, the second row becomes the column just inside it, and the bottom row becomes the leftmost column. Every cell keeps its value and its neighbours; only the orientation changes.

Because rows become columns, a matrix with rows rows and cols columns turns into one with cols rows and rows columns, just like a transpose. The difference is the direction each row is read into its column. Use the Clockwise and Counter-clockwise toggle above to watch the same grid turn both ways.

Clockwise, row i of A becomes column rows − 1 − i of the result, so the top row lands in the last column:

B = new matrix[cols][rows]
for i in 0 .. rows-1:
  for j in 0 .. cols-1:
    B[j][rows-1-i] = A[i][j]
return B

Counter-clockwise, column j of A becomes row cols − 1 − j of the result, so the write is B[cols-1-j][i] = A[i][j]. Both versions do one read and one write per cell, rows × cols steps in all. The − 1 is there because indices start at 0: in a matrix with 3 rows the last row is row 2.

A square matrix can be rotated without a second copy, and this is the version interviewers ask for. Clockwise is a transpose followed by reversing every row:

transpose(A)          # A[i][j] <-> A[j][i] for j > i
for each row of A:
  reverse(row)        # two pointers swapping inwards

Counter-clockwise is a transpose followed by reversing every column, or, if you prefer, reverse every row first and then transpose. The order matters: reverse the rows before transposing and a clockwise recipe turns into a counter-clockwise one. The other classic in-place method moves four cells at a time around each ring of the matrix, which is the same idea as a spiral traversal with a four-way swap.

• Images. An image is a matrix of pixels, and rotating it a quarter turn is exactly this loop.
• Games. Tetris pieces, jigsaw tiles and dungeon rooms are small matrices that get rotated on the fly.
• Puzzles. Checking a board against its four rotations finds positions that are really the same.
• Interviews. Rotate Image is one of the most asked matrix questions, and the in-place version is the one to know.

• Rotating the wrong way. Clockwise uses rows − 1 − i on the column index; counter-clockwise uses cols − 1 − j on the row index. Mixing them gives a transpose or a mirror instead.
• Keeping the old shape. The result of a 3 × 4 rotation is 4 × 3. Allocate it that way.
• Reversing before transposing. In the in-place recipe the order decides the direction.

Every rotation costs one step per cell. See how that growth compares with other algorithms: Big-O Playground →