43. Rotate a Matrix by 90 Degrees

Given an n x n matrix, rotate it 90 degrees clockwise in place. Print the rotated matrix, one row per line, space-separated.

Input: The first line contains an integer n. The next n lines each contain n space-separated integers, the rows of the matrix. Output: Print the rotated matrix, one row per line, space-separated.

1 <= n <= 500

This 'decompose a complex geometric transformation into two simpler, well-understood steps (transpose + reverse)' pattern is a broadly reusable trick for other matrix-transformation problems too, not just rotation.

Rotate a square grid 90 degrees clockwise, directly within the same grid (no separate output grid). Brute force: Build a brand new matrix, directly computing each cell's new position with rotation index formulas - this works but uses O(n²) extra space for the new grid, when the rotation can be done directly within the original grid instead. Optimised: The 'transpose then reverse each row' trick achieves the exact same rotation using only the ORIGINAL matrix's own memory - no second grid needed at all, since both the transpose and the row-reversal can be done with simple in-place swaps.

Allocate a brand new n x n matrix, and for every cell (i, j) in the original matrix, compute its destination position in the rotated matrix (new[j][n-1-i] = old[i][j] for a clockwise rotation) and copy the value there. This is easy to reason about because the source-to-destination mapping is a direct formula, but it uses a full second matrix's worth of memory when the problem asks for an in-place rotation. Time: O(n^2) Space: O(n^2)

Process the matrix one square ring/layer at a time from the outside in, and for each group of four corresponding cells in a ring, cyclically swap their four values directly (top goes to right, right goes to bottom, bottom goes to left, left goes to top) using one temporary variable. This achieves the rotation using only the original matrix's storage, removing the need for the brute force's second matrix, though the four-way index bookkeeping for each ring is easy to get subtly wrong. Time: O(n^2) Space: O(1)

First transpose the matrix in place (swap matrix[i][j] with matrix[j][i] for all i < j), then reverse each row in place. The composition of these two simple, well-understood linear operations produces exactly the same 90-degree clockwise rotation as the layer-cycling approach, but it's implemented as two clean, easy-to-verify passes with straightforward sequential memory access instead of intricate four-way index juggling, making it less error-prone while keeping the same time and space bounds. Time: O(n^2) Space: O(1)

1. First, TRANSPOSE the matrix: swap every element at (row, column) with the element at (column, row), flipping the grid along its main diagonal. 2. Then, REVERSE every individual row of the transposed matrix. 3. The combination of transpose-then-reverse-each-row produces exactly a 90-degree clockwise rotation.

Time: O(n²) - every cell of the matrix is touched a small, constant number of times (once during transpose, once during row reversal). Space: O(1) - the rotation happens directly within the original matrix, no extra grid needed.

Test n = 1 (matrix unchanged) and n = 500 (largest case) for performance.

Be ready to explain (or even prove with a small example) why transpose-then-reverse-rows specifically produces a CLOCKWISE rotation, and how reversing columns instead would produce a counter-clockwise one - interviewers often ask you to derive this rather than just state it.