Rotate Image

Q: What is the time and space complexity of rotating a matrix?

Rotating an n × n matrix takes O(n²) time, since nearly every value has to move once. The transpose-and-reverse method needs O(1) extra space. Building a rotated copy also takes O(n²) time but uses O(n²) extra space.

MediumArrays and strings Math and simulation

+10

You are handed an n × n grid of integers, one list per row. Rotate it a quarter turn clockwise and return it. The top row becomes the rightmost column, the second row the column to its left, and so on: the value at (i, j) lands at (j, n-1-i). You may change the grid in place; return it.

Function

rotateImage(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: the square grid, one inner list per row
Returnsinteger-2d-array: the matrix turned 90 degrees clockwise

Constraints

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

Examples

Input: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Output: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Explanation: The first row, 3 7 1, becomes the last column, read from top to bottom. The first column, 3 9 4, read from bottom to top, becomes the first row [4, 9, 3]. The centre value 5 stays put.

Follow-up

Which two in-place steps turn the matrix by 180 degrees, and can you do it in one pass of swaps?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Where each value goes is a formula: (i, j) moves to (j, n-1-i). The hard part is moving values without a second matrix, because writing a value into its new cell overwrites one that has not moved yet. A transpose followed by a row reversal makes the same quarter turn out of pair swaps.

Build a rotated copy

Intuition

Row i becomes column n-1-i, and the value at position j in the row lands at position j down that column, which is row j. So result[j][n-1-i] = matrix[i][j]. In the first example the 4 at row 2, column 0 goes to row 0, column 0, which is why the answer starts with 4.

The values move along cycles of four, so writing in place would erase a value before it moves: the 3 would overwrite the 1 in the top right corner. The copy costs n² extra cells, 4,900 for n = 70.

Algorithm

Create an n × n result matrix.
For every row i and column j, copy matrix[i][j] into result[j][n-1-i].
Return the result.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

Transpose, then reverse each row

Intuition

A transpose moves (i, j) to (j, i), and reversing a row moves column c to column n-1-c. Together they send (i, j) to (j, n-1-i), exactly where the rotation puts it.

Both moves run in place because each is a set of pair swaps. In a transpose, matrix[i][j] and matrix[j][i] each belong in the other's cell, so one swap finishes both. Swap only the pairs with j > i, or every pair is swapped back. Reversing a row swaps its two ends and walks inward.

On the first example the transpose gives [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: each row now holds a former column. Reversing each row gives the answer.

The transpose makes n(n-1)/2 swaps and the reversals n·⌊n/2⌋, so the work is O(n²) with a few variables of extra memory. The R version first copies the input into an R matrix, so its extra memory is O(n²).

Algorithm

For every cell above the main diagonal, (i, j) with j > i, exchange its value with the cell (j, i).
For each row, swap its first and last values and walk both ends inward until they meet.
Return the matrix.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

Pitfalls and edge cases

Transposing with j starting at 0. Each pair gets exchanged twice, which cancels the transpose, so the result is only the rows reversed, a mirror image.
Reversing before transposing. That order turns the matrix counterclockwise. A 2 × 2 test catches it: [[1, 2], [3, 4]] must become [[3, 1], [4, 2]].
Writing matrix[j][n-1-i] = matrix[i][j] into the same matrix. The target cell still holds a value that has not moved, and it is lost.
Using n-i instead of n-1-i. With 0-based indices the last column is n-1, so n-i runs past the end for i = 0.

Frequently asked questions3

What is the time and space complexity of rotating a matrix?

Rotating an n × n matrix takes O(n²) time, since nearly every value has to move once. The transpose-and-reverse method needs O(1) extra space. Building a rotated copy also takes O(n²) time but uses O(n²) extra space.

How do you rotate a matrix counterclockwise?

Swap the order of the two steps: reverse each row first, then transpose. You can also transpose and then reverse the order of the rows. Either way the value at (i, j) ends at (n-1-j, i).

Can you rotate a matrix by moving four values at a time?

Yes. Every value outside the centre belongs to a cycle of four cells: (i, j), (j, n-1-i), (n-1-i, n-1-j) and (n-1-j, i). Ring by ring, hold one value of each cycle in a variable and shift the other three. It has the same O(n²) time and O(1) space, with more index arithmetic to get wrong.

def rotateImage(matrix):
    # Write code here

Test #1

Test #2

Argument

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

Expected Output

[[4, 9, 3], [8, 5, 7], [6, 2, 1]]