Rotate Image
You are given an $n \times n$ 2D matrix representing an image. Rotate the image by 90 degrees (clockwise) in place.
Why Interviewers Ask This
Airbnb asks this to evaluate a candidate's mastery of in-place matrix manipulation and spatial reasoning. They specifically look for the ability to optimize space complexity to O(1) while maintaining code clarity. This problem tests if you can visualize geometric transformations without relying on extra data structures, a critical skill for performance-sensitive engineering roles.
How to Answer This Question
1. Clarify constraints: Confirm the input is always square (n x n) and whether rotation must be strictly in-place. 2. Visualize the transformation: Draw a small 3x3 grid on your whiteboard or scratchpad to trace how indices move from (i, j) to (j, n-1-i). 3. Identify the pattern: Notice that rows become columns; specifically, the first row becomes the last column. 4. Propose the two-step approach: First, transpose the matrix by swapping elements across the main diagonal (swap matrix[i][j] with matrix[j][i]). Second, reverse each row horizontally to achieve the 90-degree clockwise rotation. 5. Analyze complexity: Explicitly state that time complexity is O(n^2) because every element is visited once, and space complexity is O(1) since no new matrix is created. 6. Walk through an example: Trace the logic with a concrete 3x3 array to ensure correctness before coding.
Key Points to Cover
- Explicitly stating the O(1) space complexity constraint
- Demonstrating the two-step logic (transpose then reverse)
- Using a visual example to explain index mapping
- Confirming the input is a square matrix
- Discussing time complexity analysis
Sample Answer
To rotate this image 90 degrees clockwise in place, I'll use a two-step strategy that avoids allocating extra memory. First, let's consider a 3x3 example where the top row [1, 2, 3] needs to become the rightmost column. If we simply transpose the matrix, swapping elements across the main diagonal, the first row becomes the first column. For our example, after transposing, the matrix looks like [[1, 4, 7], [2, 5, 8], [3, 6, 9]]. However, this represents a 90-degree counter-clockwise rotation relative to the original orientation if we just swapped diagonals. To fix this and get the correct clockwise rotation, we need to reverse each row of the transposed matrix. Reversing the rows of our transposed result gives us [[7, 4, 1], [8, 5, 2], [9, 6, 3]], which matches the desired output. This approach is efficient because it only requires nested loops to swap elements twice. The time complexity is O(n^2) as we iterate through all n squared elements, and the space complexity remains O(1) since we modify the input directly. This aligns well with Airbnb's focus on building scalable, resource-efficient systems where minimizing memory overhead is crucial for handling large datasets.
Common Mistakes to Avoid
- Creating a new matrix instead of modifying in-place, violating the core constraint
- Attempting a complex single-pass swap formula without verifying edge cases
- Confusing clockwise rotation with counter-clockwise rotation logic
- Failing to handle the transpose step correctly before reversing rows
Practice This Question with AI
Answer this question orally or via text and get instant AI-powered feedback on your response quality, structure, and delivery.