Rotate a square matrix 90° clockwise in place — interview question

Rotate an n × n matrix by 90 degrees clockwise, changing the matrix itself. Do not build a second n × n matrix. Print the rotated matrix.

Constraints

1 ≤ n ≤ 300
−10^6 ≤ each value ≤ 10^6

Input and output

Input: First line: n. Then n lines of n integers each.
Output: n lines, each with n integers separated by single spaces.

Examples

Input 1

Output

7 4 1
8 5 2
9 6 3

The first row 1 2 3 becomes the last column, read top to bottom.

Input 2

2
1 2
3 4

Output

3 1
4 2

3 moves to the top-left and 2 to the bottom-right.

Show hints

After a clockwise turn, the first row becomes the last column.
Try two simple in-place steps: a transpose (swap across the main diagonal), then something done to every row.

Show the explanation

Transpose, then mirror each row.

Transpose. Swap m[i][j] with m[j][i] for every j > i. Rows become columns.
Reverse every row. Swap m[i][j] with m[i][n-1-j].

Check with the corner: the top-left value m[0][0] goes to m[0][0] in the transpose, then to m[0][n-1] after the row is reversed. That is the top-right corner, which is correct for a clockwise turn. In general the value at (r, c) ends up at (c, n-1-r).

Both steps are plain swaps, so the extra memory is O(1) and the time is O(n²), which is optimal because every cell must move. For an anticlockwise turn, transpose and then reverse each column (or reverse each row first, then transpose). A common bug is running the transpose loop over all j instead of j > i: every pair is then swapped twice and the matrix does not change.

Original UniCircle question. Last reviewed 22 Oct 2026.