Rotate Image

Rotate Image is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the In-place Rotation subpattern.

Problem statement

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]]

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

Constraints:

- n == matrix.length == matrix[i].length

- 1 <= n <= 20

- -1000 <= matrix[i][j] <= 1000

Topics and companies

Topics: Array, Math, Matrix.

Reported in interviews at Amazon, Microsoft, Apple, Uber, Cisco, Facebook, Rubrik, Adobe, Nvidia, Google, Quora, eBay and others.

How to practise Rotate Image on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n^2) — Both the transpose and row-reversal steps each visit every element of the n x n matrix once. time and O(1) — The rotation is performed in-place, using only a constant amount of extra space for temporary variables. space.

Open Rotate Image in the code editor, or read the Rotate Image editorial for a worked solution with its approach and complexity analysis.

Where Rotate Image sits in the DSA pattern sheet

• Array/Matrix Manipulation Patterns pattern guide
• In-place Rotation subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Rotate Image

Other problems that use the same In-place Rotation and Array/Matrix Manipulation Patterns techniques:

• Rotate Array — Medium, same subpattern
• Transpose Matrix — Easy, same subpattern
• Add Binary — Easy, same pattern
• Add to Array-Form of Integer — Easy, same pattern
• Diagonal Traverse — Medium, same pattern
• Find All Duplicates in an Array — Medium, same pattern