Quick Overview

A coding exercise that rotates an n by n integer matrix 90 degrees clockwise and returns the result. It tests the index mapping between rows and columns, small edge cases such as a one-by-one matrix, and the ability to perform the rotation in place with constant extra memory.

Rotate a Square Matrix 90 Degrees Clockwise

Company: Microsoft

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

Given an `n × n` matrix of integers, rotate it 90 degrees clockwise. After the rotation, the first row of the result is the original first column read from bottom to top, the second row is the original second column read from bottom to top, and so on. The report describes this second problem of the assessment only as a medium problem on rotating a matrix 90 degrees clockwise; it is rebuilt here as the standard square-matrix version. The usual expectation is to rotate the matrix in place, using only a constant amount of memory beyond the matrix itself, so be ready to meet that requirement. The console checks only the matrix you return. ### Function Signature ```python def rotate_clockwise(matrix: list[list[int]]) -> list[list[int]]: ``` ### Rules - `matrix` has `n` rows, each with `n` integers. - Return the rotated matrix: the element at row `i`, column `j` of the input ends up at row `j`, column `n - 1 - i` of the result, with rows and columns numbered from 0. - You may modify `matrix` and return it; the in-place version with constant extra memory is the intended one. ### Constraints - `1 <= n <= 100` - `-1000 <= matrix[i][j] <= 1000` ### Examples **Example 1** ```text Input: matrix = [[1, 2], [3, 4]] Output: [[3, 1], [4, 2]] ``` The first column, read from bottom to top, is `3, 1`; the second column is `4, 2`. **Example 2** ```text Input: matrix = [[2, -1, 0], [5, 7, 3], [-4, 8, 6]] Output: [[-4, 5, 2], [8, 7, -1], [6, 3, 0]] ``` The columns of the input, each read from bottom to top, are `-4, 5, 2`, then `8, 7, -1`, then `6, 3, 0`. The center element `7` stays in place. **Example 3** ```text Input: matrix = [[5]] Output: [[5]] ``` A one-by-one matrix is unchanged.

Overview: A coding exercise that rotates an n by n integer matrix 90 degrees clockwise and returns the result. It tests the index mapping between rows and columns, small edge cases such as a one-by-one matrix, and the ability to perform the rotation in place with constant extra memory.

Given an `n x n` matrix of integers, rotate it 90 degrees clockwise and return the rotated matrix. After the rotation, the first row of the result is the original first column read from bottom to top, the second row is the original second column read from bottom to top, and so on. Precisely, with rows and columns numbered from 0, the element at row `i`, column `j` of the input ends up at row `j`, column `n - 1 - i` of the result. Return the whole `n x n` result as a list of rows, from row 0 to row `n - 1`, each row listing its values from column 0 to column `n - 1`. You may modify `matrix` and return it. The intended solution rotates the matrix in place, using only a constant amount of extra memory beyond the matrix itself, but only the matrix you return is checked. ### Constraints - `matrix` has `n` rows, each with exactly `n` integers - `1 <= n <= 100` - `-1000 <= matrix[i][j] <= 1000` (every value fits in a 32-bit signed integer; no value can exceed 2^31 - 1) ### Example 1 ```text Input: matrix = [[1, 2], [3, 4]] Output: [[3, 1], [4, 2]] ``` The first column, read from bottom to top, is `3, 1`; the second column is `4, 2`. ### Example 2 ```text Input: matrix = [[2, -1, 0], [5, 7, 3], [-4, 8, 6]] Output: [[-4, 5, 2], [8, 7, -1], [6, 3, 0]] ``` The columns of the input, each read from bottom to top, are `-4, 5, 2`, then `8, 7, -1`, then `6, 3, 0`. The center element `7` stays in place.

Constraints

  • matrix has n rows, each with exactly n integers
  • 1 <= n <= 100
  • -1000 <= matrix[i][j] <= 1000

Examples

Input: ([[5]],)

Expected Output: [[5]]

Explanation: Source example 3: a 1x1 matrix is returned unchanged.

Input: ([[-1000]],)

Expected Output: [[-1000]]

Explanation: 1x1 matrix holding the lower value bound -1000 is returned unchanged.

Hints

  1. Start from the stated rule: the element at row i, column j moves to row j, column n - 1 - i. Check it by hand against Example 1 before writing any loops.
  2. Row r of the result is column r of the input read from bottom to top. Which input cell supplies result[r][c]?
  3. If you rotate in place, make sure every value has been copied to its destination before the cell holding it is overwritten.

Loading coding console...

Show the approach

Approach

Algorithm: transpose the matrix in place, then reverse every row in place.

Invariant and correctness: after the transpose pass, cell (j, i) holds the original matrix[i][j]; the pass visits each unordered pair of off-diagonal cells (i, j) with i < j exactly once and swaps the two values, so no value is overwritten before it has been moved, and diagonal cells stay where they are. Reversing row j then moves the value in column i to column n - 1 - i. Combined, the original matrix[i][j] ends at row j, column n - 1 - i, which is exactly the required clockwise rule; equivalently, row r of the result is column r of the input read from bottom to top.

Edge cases: n = 1 performs no swaps and returns the single value unchanged; for odd n the center cell (n // 2, n // 2) is fixed by both passes; duplicate, zero and negative values need no special handling because values are only moved, never compared or combined, and every value stays within -1000..1000. The Python, JavaScript and Java references rotate in place with O(1) extra memory; the C++ reference first copies its const input and then applies the same two passes to the copy.

Time complexity:
O(n^2)
Space complexity:
O(1) extra space beyond the matrix when rotating in place