Rotate a Matrix In Place
Company: Apple
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an `n x n` matrix of integers, rotate the matrix 90 degrees clockwise.
Implement the function in Python. You may use a straightforward approach with loops, but the preferred solution should rotate the matrix in place without allocating another `n x n` matrix.
Example:
```python
Input:
[
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
Output:
[
[7, 4, 1],
[8, 5, 2],
[9, 6, 3]
]
```
Discuss the time and space complexity of your approach.
Overview: This question evaluates proficiency in in-place matrix and array manipulation, spatial data transformation, and reasoning about time and space complexity.
Given an n x n matrix of integers, rotate the matrix 90 degrees clockwise.
Return the rotated matrix. The preferred solution modifies the matrix in place without allocating another n x n matrix, although straightforward loop-based reasoning is acceptable.
For example, rotating
[[1, 2, 3],
[4, 5, 6],
[7, 8, 9]]
produces
[[7, 4, 1],
[8, 5, 2],
[9, 6, 3]].
Constraints
- 0 <= n <= 200
- -10^9 <= matrix[i][j] <= 10^9
- The input matrix is square (has exactly n rows and n columns)
Examples
Input: ([[1, 2, 3], [4, 5, 6], [7, 8, 9]],)
Expected Output: [[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Explanation: The first column becomes the first row in reverse order, producing the 90-degree clockwise rotation.
Input: ([[5, 1, 9, 11], [2, 4, 8, 10], [13, 3, 6, 7], [15, 14, 12, 16]],)
Expected Output: [[15, 13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7, 10, 11]]
Explanation: Each layer of the 4x4 matrix shifts clockwise, yielding the rotated matrix.
Hints
- Track where each value moves: an element at row r, column c ends up at row c, column n - 1 - r after a clockwise rotation.
- Try decomposing the rotation into two simpler in-place operations instead of moving every value directly to its final position.