Rotate Image

The problem

matrix is a square table of integers, given as a list of rows: it has as many rows as columns, and at least one cell. Rotate it a quarter turn (90 degrees) clockwise, so that the top row ends up as the right column, and return the turned matrix as a list of rows. Values may be negative and may repeat. You may build a new matrix or change matrix itself, but either way your function must return the result.

What to write

function solve(matrix: number[][]): number[][]

Input
matrix = [[1,2],[3,4]]

Output
[[3,1],[4,2]]

Input
matrix = [[1]]

Output
[[1]]

Constraints

Square integer matrix with side length 1–30.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The matrix is square, so the answer has the same shape as the input, and its side is at most 30: at most 900 cells. Visiting every cell once is cheap. You may also return a new matrix, so nothing forces you to move values around inside the given one.

2. Hint 2: Ask a smaller question

   Write the numbers 1 to 9 in a 3 × 3 square on paper, row by row, and turn the paper a quarter turn clockwise. Which three numbers are in the top row now, and in what order? Where were those three numbers before you turned the paper?

3. Hint 3: Name the pattern

   A value's new cell depends only on its old row and column: the left column, read from the bottom up, becomes the top row. So one walk over the cells with a rule for the positions does the job. Visiting every cell in a planned order, by row and column, is matrix traversal. Read the lesson on matrix traversal.

4. Hint 4: State the invariant

   Count rows and columns from 0 and call the side length n. Row r of the answer is always column r of the input, read from the bottom row up. So the cell at row r, column c of the answer gets the value at row n - 1 - c, column r of the input.

5. Hint 5: Sketch the pseudocode

   n = number of rows. answer = empty list. For r from 0 to n - 1: start an empty row; for c from 0 to n - 1, add the value at row n - 1 - c, column r of matrix to that row; then add the row to answer. Return answer.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Map output row r and column c to input row n - 1 - c and column r. This constructs a clockwise rotation without overwriting unread input.

The slow way

Move the values inside matrix itself: go through the cells and write into each one the value that belongs there after the turn. It goes wrong at once, because a write destroys a value that another cell still needs. For [[1, 2], [3, 4]] this gives [[3, 3], [4, 3]]: the 1 is overwritten before it is read.

The insight

Turn the square a quarter turn clockwise and its left column lies along the top, with the bottom value first. Every other column becomes a row in the same way. So each row of the answer can be read straight off the input: row 0 is column 0 of the input, row 1 is column 1, and so on, each read from the bottom up.

Step by step

1. Note the side length and start a new matrix for the answer. Writing into a new matrix leaves matrix untouched, so every value is still there when it is read. The side length is needed to count rows from the bottom.
2. Build the answer one row at a time, from the top row down. Each row of the answer comes from one column of the input and from nothing else, so the rows can be built one after another.
3. Fill the row with the input column of the same number, bottom up. The turn lays that column along this row with its bottom value first. With rows counted from 0 and a side of n, the cell in column c takes its value from row n - 1 - c.
4. Add the finished row to the answer. Rows are added in the order they are built, top row first, so each one ends up at its own row number in the answer.
5. Return the new matrix. The answer is what the function returns. By now every cell of the new matrix holds the value that the turn brings there.

The same numbered steps are the comments in each solution.

function solve(matrix) {
  // 1. Note the side length and start a new matrix for the answer
  const n = matrix.length,
    out = [];
  // 2. Build the answer one row at a time, from the top row down
  for (let r = 0; r < n; r++) {
    const row = [];
    // 3. Fill the row with the input column of the same number, bottom up
    for (let c = 0; c < n; c++) row.push(matrix[n - 1 - c][r]);
    // 4. Add the finished row to the answer
    out.push(row);
  }
  // 5. Return the new matrix
  return out;
}

function solve(matrix: number[][]): number[][] {
  // 1. Note the side length and start a new matrix for the answer
  const n = matrix.length,
    out: number[][] = [];
  // 2. Build the answer one row at a time, from the top row down
  for (let r = 0; r < n; r++) {
    const row: number[] = [];
    // 3. Fill the row with the input column of the same number, bottom up
    for (let c = 0; c < n; c++) row.push(matrix[n - 1 - c][r]);
    // 4. Add the finished row to the answer
    out.push(row);
  }
  // 5. Return the new matrix
  return out;
}

def solve(matrix):
    # 1. Note the side length and start a new matrix for the answer
    n = len(matrix)
    out = []
    # 2. Build the answer one row at a time, from the top row down
    for r in range(n):
        row = []
        # 3. Fill the row with the input column of the same number, bottom up
        for c in range(n):
            row.append(matrix[n - 1 - c][r])
        # 4. Add the finished row to the answer
        out.append(row)
    # 5. Return the new matrix
    return out

Example 1, traced

Input
matrix = [[1,2],[3,4]]

Output
[[3,1],[4,2]]

Why it works

Counting from 0, a quarter turn clockwise moves the value at row i, column j to row j, column n - 1 - i. The code fills answer row r, column c from input row n - 1 - c, column r, and by that rule this value belongs at row r, column c. The input is never written to, so every read sees an original value.

Time and space

Time O(n²), extra space O(n²) output. The answer has n × n cells and each is filled once with one read, so the time is O(n²). The new matrix is the output and holds n² values: that is the O(n²) space. Turning the values inside matrix would save that memory but is harder to get right.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Do not write into matrix while you still read from it. Copying only the outer list does not help, because its rows are still the rows of matrix: [[1, 2], [3, 4]] then comes back as [[3, 3], [4, 3]].
• Read the column from the bottom up. Reading it from the top down gives [[1, 3], [2, 4]] for the first example: the matrix flipped over its diagonal, not turned.
• Return the matrix. The tests compare what your function returns, so a function that turns matrix correctly but returns nothing fails every test.

Pattern

Matrix traversal.

Keep going