MediumMatrix

Rotate a Matrix

Q: Why does std::mem::swap(&mut matrix[i][j], &mut matrix[j][i]) not compile?

Both arguments borrow matrix mutably at the same time, and the borrow checker cannot see that they point into different rows. split_at_mut(j) splits the outer Vec into two slices that are known not to overlap, so one cell can come from each. For i32 a plain three-line swap through a temporary also works, because reading a Copy value ends the borrow.

Q: Why take mut matrix instead of &mut Vec >?

The signature here takes the Vec by value and returns the rotated one, so the function owns it and mut on the parameter is enough to change it in place and move it back out. With a &mut Vec > signature the same loops work unchanged and nothing is returned.

Q: Can n - 1 - first underflow?

In this debug build a usize subtraction below zero panics. The ring loop runs only for first < n / 2, so n is at least 2 there and n - 1 - first stays positive. With n = 0 the loop body never runs, so n - 1 is never computed.

Q: Is there an iterator one-liner for transpose and reverse?

For a new matrix, yes: (0..n).map(|c| matrix.iter().rev().map(|row| row[c]).collect()).collect() reads each column bottom to top as a row, which is the clockwise turn. It allocates a new Vec per row, like the first approach.

Q: How do I rotate counter-clockwise?

Transpose, then matrix.reverse() on the outer Vec instead of each row: that only swaps the row Vec headers, no cells move. In the copy version, cell [r][c] comes from matrix[c][n - 1 - r].

You get a square matrix matrix of integers with n rows and n columns. Rotate it 90 degrees clockwise and return the rotated matrix. After the turn, the first column read from bottom to top is the first row, and the first row read from left to right is the last column: the value at row i, column j moves to row j, column n - 1 - i.

You may rotate the matrix in place and return the same array, or build a new one and return that; only the returned matrix is checked. An empty matrix (n = 0) returns an empty array, and a 1 × 1 matrix comes back unchanged.

Examples

Input

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

Output[[5, 3, 7], [8, 9, 1], [6, 2, 4]]WhyThe first column read bottom to top, 5, 3, 7, becomes the first row. The centre 9 stays where it is.

Input

matrix = [[10, 11, 12, 13], [14, 15, 16, 17], [18, 19, 20, 21], [22, 23, 24, 25]]

Output[[22, 18, 14, 10], [23, 19, 15, 11], [24, 20, 16, 12], [25, 21, 17, 13]]WhyThe top row 10, 11, 12, 13 becomes the last column, top to bottom. The inner 2 × 2 block 15, 16, 19, 20 turns too.

Constraints

Size: 0 ≤ n ≤ 64, matrix is n × n
Values: -10⁴ ≤ matrix[i][j] ≤ 10⁴
Answer: Clockwise; in place or a new matrix, only the return value counts.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

Build an empty n × n grid with a list comprehension, then copy every value to where the turn sends it: row i, column j lands at row j, column n - 1 - i. Each cell is written once, and the input is left as it was.

def rotate(matrix: list[list[int]]) -> list[list[int]]:
    n = len(matrix)
    result = [[0] * n for _ in range(n)]  # n separate rows, not n copies of one
    for i in range(n):
        for j in range(n):
            result[j][n - 1 - i] = matrix[i][j]
    return result

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap every cell above the main diagonal with its mirror below it, which turns rows into columns. The transposed matrix is the rotation seen in a mirror, so reversing each row with row.reverse() finishes the clockwise turn. Tuple assignment does each swap without a temporary, and no second matrix is needed.

def rotate(matrix: list[list[int]]) -> list[list[int]]:
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):  # above the diagonal only, or every pair swaps back
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()
    return matrix

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Treat the matrix as rings, from the outer border inwards. On each ring, one value from the top edge is saved, then the left, bottom and right values each move one corner clockwise, and the saved top value fills the right edge. Every cell moves exactly once, and only one temporary variable is used. With an odd n the centre cell belongs to no ring and stays put.

def rotate(matrix: list[list[int]]) -> list[list[int]]:
    n = len(matrix)
    for first in range(n // 2):
        last = n - 1 - first
        for i in range(first, last):
            offset = i - first
            top = matrix[first][i]
            matrix[first][i] = matrix[last - offset][first]           # left -> top
            matrix[last - offset][first] = matrix[last][last - offset]  # bottom -> left
            matrix[last][last - offset] = matrix[i][last]             # right -> bottom
            matrix[i][last] = top                                     # top -> right
    return matrix

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

Array.from with a mapping callback creates n separate rows, each a fresh Array(n). Two loops then copy the value at row i, column j to row j, column n - 1 - i. The input array is not touched.

function rotate(matrix) {
  const n = matrix.length;
  const result = Array.from({ length: n }, () => new Array(n));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      result[j][n - 1 - i] = matrix[i][j];
    }
  }
  return result;
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap each cell above the main diagonal with its mirror, using destructuring assignment [a, b] = [b, a], so rows become columns. Then row.reverse() flips each row in place, which turns the transpose into a clockwise rotation. The inner loop starts at i + 1, otherwise every pair would be swapped twice and end up where it started.

function rotate(matrix) {
  const n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
    }
  }
  for (const row of matrix) row.reverse();
  return matrix;
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Work ring by ring from the border inwards. For each position on a ring's top edge, save the top value, move the left value up, the bottom value left, the right value down, and put the saved value on the right. Every cell moves once with a single temporary. When n is odd the centre cell sits in no ring and stays where it is.

function rotate(matrix) {
  const n = matrix.length;
  for (let first = 0; first < Math.floor(n / 2); first++) {
    const last = n - 1 - first;
    for (let i = first; i < last; i++) {
      const offset = i - first;
      const top = matrix[first][i];
      matrix[first][i] = matrix[last - offset][first];           // left -> top
      matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
      matrix[last][last - offset] = matrix[i][last];             // right -> bottom
      matrix[i][last] = top;                                     // top -> right
    }
  }
  return matrix;
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

Create n independent rows with Array.from, typed as number[][], then copy the value at row i, column j to row j, column n - 1 - i. The input stays as it was.

function rotate(matrix: number[][]): number[][] {
  const n = matrix.length;
  const result: number[][] = Array.from({ length: n }, () => new Array<number>(n));
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      result[j][n - 1 - i] = matrix[i][j];
    }
  }
  return result;
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap each cell above the main diagonal with its mirror, which makes rows into columns, then reverse every row in place with row.reverse(). The two steps together are a clockwise turn, and nothing but the swaps touches memory.

function rotate(matrix: number[][]): number[][] {
  const n = matrix.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const t = matrix[i][j];
      matrix[i][j] = matrix[j][i];
      matrix[j][i] = t;
    }
  }
  for (const row of matrix) row.reverse();
  return matrix;
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Rotate ring by ring from the outside in. For each step along a ring's top edge, save the top value, then move left to top, bottom to left and right to bottom, and drop the saved value on the right. Each cell moves once; an odd n leaves the centre cell where it is.

function rotate(matrix: number[][]): number[][] {
  const n = matrix.length;
  for (let first = 0; first < Math.floor(n / 2); first++) {
    const last = n - 1 - first;
    for (let i = first; i < last; i++) {
      const offset = i - first;
      const top = matrix[first][i];
      matrix[first][i] = matrix[last - offset][first];           // left -> top
      matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
      matrix[last][last - offset] = matrix[i][last];             // right -> bottom
      matrix[i][last] = top;                                     // top -> right
    }
  }
  return matrix;
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

new int[n][n] allocates a zero-filled square, every row its own array. Two loops then copy the value at row i, column j to row j, column n - 1 - i. For n = 0 the result is an empty array, which is what the tests expect.

import java.util.*;

public class Main {
    static int[][] rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] result = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[j][n - 1 - i] = matrix[i][j];
            }
        }
        return result;
    }
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap every cell above the main diagonal with its mirror, so rows become columns, then reverse each row with two indices walking towards each other. Java has no in-place reverse for an int[] (Collections.reverse needs a List), so the swap loop is written out.

import java.util.*;

public class Main {
    static int[][] rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) { // above the diagonal only
                int t = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = t;
            }
        }
        for (int[] row : matrix) {
            for (int lo = 0, hi = n - 1; lo < hi; lo++, hi--) {
                int t = row[lo];
                row[lo] = row[hi];
                row[hi] = t;
            }
        }
        return matrix;
    }
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Rotate the rings from the border inwards. For each position along a ring's top edge, keep the top value in top, move left to top, bottom to left and right to bottom, then write top on the right. Each cell moves once, and an odd n leaves the centre cell alone.

import java.util.*;

public class Main {
    static int[][] rotate(int[][] matrix) {
        int n = matrix.length;
        for (int first = 0; first < n / 2; first++) {
            int last = n - 1 - first;
            for (int i = first; i < last; i++) {
                int offset = i - first;
                int top = matrix[first][i];
                matrix[first][i] = matrix[last - offset][first];           // left -> top
                matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
                matrix[last][last - offset] = matrix[i][last];             // right -> bottom
                matrix[i][last] = top;                                     // top -> right
            }
        }
        return matrix;
    }
}

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

make([][]int, n) only creates the outer slice; each row is nil until the loop gives it its own make([]int, n). Then the value at row i, column j is copied to row j, column n-1-i, and the input is left alone.

package main

func rotate(matrix [][]int) [][]int {
	n := len(matrix)
	result := make([][]int, n)
	for i := range result {
		result[i] = make([]int, n)
	}
	for i, row := range matrix {
		for j, v := range row {
			result[j][n-1-i] = v
		}
	}
	return result
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap each cell above the main diagonal with its mirror using Go's tuple assignment, which turns rows into columns. Then slices.Reverse flips every row in place. A range over the outer slice hands out row headers that share their backing arrays with matrix, so reversing row reverses the real row.

package main

import "slices"

func rotate(matrix [][]int) [][]int {
	n := len(matrix)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ { // above the diagonal only
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}
	for _, row := range matrix {
		slices.Reverse(row)
	}
	return matrix
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Walk the rings from the outside in. For each step along a ring's top edge, one four-way tuple assignment moves left to top, bottom to left, right to bottom and top to right in a single statement: Go evaluates every right-hand value before it assigns, so no temporary is needed. An odd n leaves the centre cell alone.

package main

func rotate(matrix [][]int) [][]int {
	n := len(matrix)
	for first := 0; first < n/2; first++ {
		last := n - 1 - first
		for i := first; i < last; i++ {
			off := i - first
			matrix[first][i], matrix[last-off][first], matrix[last][last-off], matrix[i][last] =
				matrix[last-off][first], matrix[last][last-off], matrix[i][last], matrix[first][i]
		}
	}
	return matrix
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

A jagged int[][] needs each row allocated on its own: new int[n][] creates n null slots, and the first loop fills them. The second loop copies the value at row i, column j to row j, column n - 1 - i.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int[][] Rotate(int[][] matrix)
    {
        int n = matrix.Length;
        var result = new int[n][];
        for (int i = 0; i < n; i++) result[i] = new int[n];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                result[j][n - 1 - i] = matrix[i][j];
            }
        }
        return result;
    }
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap each cell above the main diagonal with its mirror using a tuple swap, which turns rows into columns, then Array.Reverse(row) flips every row in place. Together the two steps are a clockwise turn with no extra matrix.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int[][] Rotate(int[][] matrix)
    {
        int n = matrix.Length;
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++) // above the diagonal only
            {
                (matrix[i][j], matrix[j][i]) = (matrix[j][i], matrix[i][j]);
            }
        }
        foreach (var row in matrix) Array.Reverse(row);
        return matrix;
    }
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Rotate the rings from the border inwards. For each step along a ring's top edge, save the top value, move left to top, bottom to left and right to bottom, and write the saved value on the right. Every cell moves once; with an odd n the centre stays where it is.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static int[][] Rotate(int[][] matrix)
    {
        int n = matrix.Length;
        for (int first = 0; first < n / 2; first++)
        {
            int last = n - 1 - first;
            for (int i = first; i < last; i++)
            {
                int offset = i - first;
                int top = matrix[first][i];
                matrix[first][i] = matrix[last - offset][first];           // left -> top
                matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
                matrix[last][last - offset] = matrix[i][last];             // right -> bottom
                matrix[i][last] = top;                                     // top -> right
            }
        }
        return matrix;
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

vector<vector<int>> result(n, vector<int>(n)) builds an n × n grid of zeros in one line. Two loops then copy the value at row i, column j to row j, column n - 1 - i, leaving the input untouched.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> rotate(vector<vector<int>>& matrix) {
        int n = (int)matrix.size();
        vector<vector<int>> result(n, vector<int>(n));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                result[j][n - 1 - i] = matrix[i][j];
            }
        }
        return result;
    }
};

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

swap each cell above the main diagonal with its mirror, which turns rows into columns, then reverse(row.begin(), row.end()) flips each row in place. The range-for takes row by reference, so the reverse changes the matrix and not a copy.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> rotate(vector<vector<int>>& matrix) {
        int n = (int)matrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) { // above the diagonal only
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        for (auto& row : matrix) reverse(row.begin(), row.end());
        return matrix;
    }
};

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Rotate the rings from the outside in. For each step along a ring's top edge, keep the top value, move left to top, bottom to left and right to bottom, then write the kept value on the right. Every cell moves once with one temporary; an odd n leaves the centre alone.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int>> rotate(vector<vector<int>>& matrix) {
        int n = (int)matrix.size();
        for (int first = 0; first < n / 2; first++) {
            int last = n - 1 - first;
            for (int i = first; i < last; i++) {
                int offset = i - first;
                int top = matrix[first][i];
                matrix[first][i] = matrix[last - offset][first];           // left -> top
                matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
                matrix[last][last - offset] = matrix[i][last];             // right -> bottom
                matrix[i][last] = top;                                     // top -> right
            }
        }
        return matrix;
    }
};

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

Allocate the result as n row pointers, each row n ints, plus the *returnColumnSizes array that tells the caller every row is n long. Two loops then copy the value at row i, column j to row j, column n - 1 - i. For n = 0 both allocations are empty and *returnSize is 0.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

/**
 * Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
 */
int** rotate(int** matrix, int matrixSize, int* matrixColSize, int* returnSize, int** returnColumnSizes) {
    int n = matrixSize;
    int** result = malloc(n * sizeof *result);
    *returnColumnSizes = malloc(n * sizeof **returnColumnSizes);
    for (int i = 0; i < n; i++) {
        result[i] = malloc(n * sizeof *result[i]);
        (*returnColumnSizes)[i] = n;
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            result[j][n - 1 - i] = matrix[i][j];
        }
    }
    *returnSize = n;
    return result;
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap every cell above the main diagonal with its mirror, so rows become columns, then reverse each row with two indices walking towards each other. The rotation itself needs no extra memory; the last step copies the rows into malloc'ed arrays with memcpy, because the caller frees what it gets back and the input's rows are not ours to hand over.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

/**
 * Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
 */
static int** copyOut(int** matrix, int n, int* returnSize, int** returnColumnSizes) {
    int** result = malloc(n * sizeof *result);
    *returnColumnSizes = malloc(n * sizeof **returnColumnSizes);
    for (int i = 0; i < n; i++) {
        result[i] = malloc(n * sizeof *result[i]);
        memcpy(result[i], matrix[i], n * sizeof *result[i]);
        (*returnColumnSizes)[i] = n;
    }
    *returnSize = n;
    return result;
}

int** rotate(int** matrix, int matrixSize, int* matrixColSize, int* returnSize, int** returnColumnSizes) {
    int n = matrixSize;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) { // above the diagonal only
            int t = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = t;
        }
    }
    for (int i = 0; i < n; i++) {
        int* row = matrix[i];
        for (int lo = 0, hi = n - 1; lo < hi; lo++, hi--) {
            int t = row[lo];
            row[lo] = row[hi];
            row[hi] = t;
        }
    }
    return copyOut(matrix, n, returnSize, returnColumnSizes);
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

/**
 * Note: the returned arrays and *returnColumnSizes must be malloc'ed; the caller frees them.
 */
static int** copyOut(int** matrix, int n, int* returnSize, int** returnColumnSizes) {
    int** result = malloc(n * sizeof *result);
    *returnColumnSizes = malloc(n * sizeof **returnColumnSizes);
    for (int i = 0; i < n; i++) {
        result[i] = malloc(n * sizeof *result[i]);
        memcpy(result[i], matrix[i], n * sizeof *result[i]);
        (*returnColumnSizes)[i] = n;
    }
    *returnSize = n;
    return result;
}

int** rotate(int** matrix, int matrixSize, int* matrixColSize, int* returnSize, int** returnColumnSizes) {
    int n = matrixSize;
    for (int first = 0; first < n / 2; first++) {
        int last = n - 1 - first;
        for (int i = first; i < last; i++) {
            int offset = i - first;
            int top = matrix[first][i];
            matrix[first][i] = matrix[last - offset][first];           // left -> top
            matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
            matrix[last][last - offset] = matrix[i][last];             // right -> bottom
            matrix[i][last] = top;                                     // top -> right
        }
    }
    return copyOut(matrix, n, returnSize, returnColumnSizes);
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

Array(n) { r -> IntArray(n) { c -> … } } builds the result cell by cell, and each cell only has to say where it comes from: row r, column c of the rotated matrix is matrix[n - 1 - c][r]. For n = 0 it is an empty array, which is what the tests expect.

class Solution {
    fun rotate(matrix: Array<IntArray>): Array<IntArray> {
        val n = matrix.size
        return Array(n) { r -> IntArray(n) { c -> matrix[n - 1 - c][r] } }
    }
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap every cell above the main diagonal with its mirror, so rows become columns, then call reverse() on each row. Unlike reversed(), which returns a new list, IntArray.reverse() flips the array in place.

class Solution {
    fun rotate(matrix: Array<IntArray>): Array<IntArray> {
        val n = matrix.size
        for (i in 0 until n) {
            for (j in i + 1 until n) { // above the diagonal only
                val t = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = t
            }
        }
        matrix.forEach { it.reverse() }
        return matrix
    }
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

class Solution {
    fun rotate(matrix: Array<IntArray>): Array<IntArray> {
        val n = matrix.size
        for (first in 0 until n / 2) {
            val last = n - 1 - first
            for (i in first until last) {
                val offset = i - first
                val top = matrix[first][i]
                matrix[first][i] = matrix[last - offset][first]           // left -> top
                matrix[last - offset][first] = matrix[last][last - offset] // bottom -> left
                matrix[last][last - offset] = matrix[i][last]             // right -> bottom
                matrix[i][last] = top                                     // top -> right
            }
        }
        return matrix
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

Two nested iterator chains collect the result row by row, and each cell only has to say where it comes from: row r, column c of the rotated matrix is matrix[n - 1 - c][r]. For n = 0 the outer range is empty and the result is vec![], which is what the tests expect.

impl Solution {
    pub fn rotate(matrix: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = matrix.len();
        (0..n)
            .map(|r| (0..n).map(|c| matrix[n - 1 - c][r]).collect())
            .collect()
    }
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

The function owns matrix, so it can take it as mut and return it. Swapping matrix[i][j] with matrix[j][i] needs two mutable borrows into different rows, which split_at_mut(j) provides: row i sits in the first half and row j starts the second. Then row.reverse() flips every row in place.

impl Solution {
    pub fn rotate(mut matrix: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = matrix.len();
        for i in 0..n {
            for j in i + 1..n {
                // above the diagonal only: rows i < j live in different halves
                let (upper, lower) = matrix.split_at_mut(j);
                std::mem::swap(&mut upper[i][j], &mut lower[0][i]);
            }
        }
        for row in matrix.iter_mut() {
            row.reverse();
        }
        matrix
    }
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Rotate the rings from the border inwards. For each position along a ring's top edge, copy the top value into top (an i32 is Copy, so no borrow is held), move left to top, bottom to left and right to bottom, then write top on the right. Every index is a usize, and last - offset never goes below zero.

impl Solution {
    pub fn rotate(mut matrix: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let n = matrix.len();
        for first in 0..n / 2 {
            let last = n - 1 - first;
            for i in first..last {
                let offset = i - first;
                let top = matrix[first][i];
                matrix[first][i] = matrix[last - offset][first]; // left -> top
                matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
                matrix[last][last - offset] = matrix[i][last]; // right -> bottom
                matrix[i][last] = top; // top -> right
            }
        }
        matrix
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

Two nested map calls over 0..<n build the result row by row, and each cell only has to say where it comes from: row r, column c of the rotated matrix is matrix[n - 1 - c][r]. For n = 0 the range is empty and the result is [].

class Solution {
    func rotate(_ matrix: [[Int]]) -> [[Int]] {
        let n = matrix.count
        return (0..<n).map { r in (0..<n).map { c in matrix[n - 1 - c][r] } }
    }
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

The parameter is a constant, so copy it into a var (Swift arrays are values; the copy is cheap until the first write). Swap every cell above the main diagonal with its mirror using a tuple assignment, then reverse() each row in place.

class Solution {
    func rotate(_ matrix: [[Int]]) -> [[Int]] {
        var m = matrix
        let n = m.count
        for i in 0..<n {
            for j in (i + 1)..<n { // above the diagonal only
                (m[i][j], m[j][i]) = (m[j][i], m[i][j])
            }
        }
        for i in m.indices {
            m[i].reverse()
        }
        return m
    }
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Rotate the rings from the border inwards. For each position along a ring's top edge, keep the top value in top, move left to top, bottom to left and right to bottom, then write top on the right. For n = 0 and n = 1 the range 0..<n / 2 is empty, so neither needs a special case.

class Solution {
    func rotate(_ matrix: [[Int]]) -> [[Int]] {
        var m = matrix
        let n = m.count
        for first in 0..<n / 2 {
            let last = n - 1 - first
            for i in first..<last {
                let offset = i - first
                let top = m[first][i]
                m[first][i] = m[last - offset][first]           // left -> top
                m[last - offset][first] = m[last][last - offset] // bottom -> left
                m[last][last - offset] = m[i][last]             // right -> bottom
                m[i][last] = top                                // top -> right
            }
        }
        return m
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

array_fill builds an n × n list of zeros (an empty array for n = 0), so every key exists in order before the loops write into it. The value at row i, column j goes to row j, column n - 1 - i.

<?php

class Solution {
    /**
     * @param int[][] $matrix
     * @return int[][]
     */
    function rotate(array $matrix): array {
        $n = count($matrix);
        $result = array_fill(0, $n, array_fill(0, $n, 0));
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $n; $j++) {
                $result[$j][$n - 1 - $i] = $matrix[$i][$j];
            }
        }
        return $result;
    }
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

PHP passes arrays by value, so $matrix is already the function's own copy to change. Swap every cell above the main diagonal with its mirror in one destructuring assignment, then replace each row with array_reverse($row), which returns the row as a fresh list.

<?php

class Solution {
    /**
     * @param int[][] $matrix
     * @return int[][]
     */
    function rotate(array $matrix): array {
        $n = count($matrix);
        for ($i = 0; $i < $n; $i++) {
            for ($j = $i + 1; $j < $n; $j++) { // above the diagonal only
                [$matrix[$i][$j], $matrix[$j][$i]] = [$matrix[$j][$i], $matrix[$i][$j]];
            }
        }
        foreach ($matrix as $i => $row) {
            $matrix[$i] = array_reverse($row);
        }
        return $matrix;
    }
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Rotate the rings from the border inwards. For each position along a ring's top edge, keep the top value in $top, move left to top, bottom to left and right to bottom, then write $top on the right. Only existing keys are overwritten, so the array stays a list in its original key order.

<?php

class Solution {
    /**
     * @param int[][] $matrix
     * @return int[][]
     */
    function rotate(array $matrix): array {
        $n = count($matrix);
        for ($first = 0; $first < intdiv($n, 2); $first++) {
            $last = $n - 1 - $first;
            for ($i = $first; $i < $last; $i++) {
                $offset = $i - $first;
                $top = $matrix[$first][$i];
                $matrix[$first][$i] = $matrix[$last - $offset][$first];            // left -> top
                $matrix[$last - $offset][$first] = $matrix[$last][$last - $offset]; // bottom -> left
                $matrix[$last][$last - $offset] = $matrix[$i][$last];              // right -> bottom
                $matrix[$i][$last] = $top;                                         // top -> right
            }
        }
        return $matrix;
    }
}

3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

Array.new(n) { |r| Array.new(n) { |c| … } } builds the result cell by cell, and each cell only has to say where it comes from: row r, column c of the rotated matrix is matrix[n - 1 - c][r]. The block form gives every row its own array, and n = 0 gives [].

# @param {Integer[][]} matrix
# @return {Integer[][]}
def rotate(matrix)
  n = matrix.size
  Array.new(n) { |r| Array.new(n) { |c| matrix[n - 1 - c][r] } }
end

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap every cell above the main diagonal with its mirror using parallel assignment, which evaluates the right-hand side before writing, then call reverse! on each row. The bang version flips the row in place; plain reverse would return a copy.

# @param {Integer[][]} matrix
# @return {Integer[][]}
def rotate(matrix)
  n = matrix.size
  n.times do |i|
    (i + 1...n).each do |j| # above the diagonal only
      matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    end
  end
  matrix.each(&:reverse!)
end

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Rotate the rings from the border inwards. For each position along a ring's top edge, one parallel assignment moves four cells at once: left to top, bottom to left, right to bottom and top to right. Ruby reads all four values before writing any, so no temporary is needed, and an odd n leaves the centre cell alone.

# @param {Integer[][]} matrix
# @return {Integer[][]}
def rotate(matrix)
  n = matrix.size
  (n / 2).times do |first|
    last = n - 1 - first
    (first...last).each do |i|
      offset = i - first
      matrix[first][i], matrix[last - offset][first], matrix[last][last - offset], matrix[i][last] =
        matrix[last - offset][first], matrix[last][last - offset], matrix[i][last], matrix[first][i]
    end
  end
  matrix
end

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

List.generate(n, …) nested twice builds the result cell by cell, and each cell only has to say where it comes from: row r, column c of the rotated matrix is matrix[n - 1 - c][r]. Every row is its own list, and n = 0 gives [].

class Solution {
  List<List<int>> rotate(List<List<int>> matrix) {
    final n = matrix.length;
    return List.generate(n, (r) => List.generate(n, (c) => matrix[n - 1 - c][r]));
  }
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap every cell above the main diagonal with its mirror, so rows become columns, then reverse each row. row.reversed is a lazy Iterable view, not an in-place flip, so a two-index loop swaps the ends towards the middle instead.

class Solution {
  List<List<int>> rotate(List<List<int>> matrix) {
    final n = matrix.length;
    for (var i = 0; i < n; i++) {
      for (var j = i + 1; j < n; j++) { // above the diagonal only
        final t = matrix[i][j];
        matrix[i][j] = matrix[j][i];
        matrix[j][i] = t;
      }
    }
    for (final row in matrix) {
      for (var lo = 0, hi = n - 1; lo < hi; lo++, hi--) {
        final t = row[lo];
        row[lo] = row[hi];
        row[hi] = t;
      }
    }
    return matrix;
  }
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

Rotate the rings from the border inwards. For each position along a ring's top edge, keep the top value in top, move left to top, bottom to left and right to bottom, then write top on the right. n ~/ 2 is integer division, the number of rings, and an odd n leaves the centre cell alone.

class Solution {
  List<List<int>> rotate(List<List<int>> matrix) {
    final n = matrix.length;
    for (var first = 0; first < n ~/ 2; first++) {
      final last = n - 1 - first;
      for (var i = first; i < last; i++) {
        final offset = i - first;
        final top = matrix[first][i];
        matrix[first][i] = matrix[last - offset][first]; // left -> top
        matrix[last - offset][first] = matrix[last][last - offset]; // bottom -> left
        matrix[last][last - offset] = matrix[i][last]; // right -> bottom
        matrix[i][last] = top; // top -> right
      }
    }
    return matrix;
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Copy every cell into a new matrix

O(n²) time · O(n²) space

Array.tabulate(n, n) builds an n × n array from a function of the row and column, so each cell only has to say where it comes from: row r, column c of the rotated matrix is matrix(n - 1 - c)(r). For n = 0 it is an empty array, which is what the tests expect.

object Solution {
  def rotate(matrix: Array[Array[Int]]): Array[Array[Int]] = {
    val n = matrix.length
    Array.tabulate(n, n)((r, c) => matrix(n - 1 - c)(r))
  }
}

2 · In place: transpose, then reverse each row

O(n²) time · O(1) space

Swap every cell above the main diagonal with its mirror, so rows become columns, then reverse each row. row.reverse would return a new array, so a small while loop swaps the two ends towards the middle instead, keeping the rotation in place.

object Solution {
  def rotate(matrix: Array[Array[Int]]): Array[Array[Int]] = {
    val n = matrix.length
    for (i <- 0 until n; j <- i + 1 until n) { // above the diagonal only
      val t = matrix(i)(j)
      matrix(i)(j) = matrix(j)(i)
      matrix(j)(i) = t
    }
    matrix.foreach(reverseInPlace)
    matrix
  }

  private def reverseInPlace(row: Array[Int]): Unit = {
    var lo = 0
    var hi = row.length - 1
    while (lo < hi) {
      val t = row(lo)
      row(lo) = row(hi)
      row(hi) = t
      lo += 1
      hi -= 1
    }
  }
}

3 · In place: rotate four cells at a time, ring by ring

O(n²) time · O(1) space

recommended

object Solution {
  def rotate(matrix: Array[Array[Int]]): Array[Array[Int]] = {
    val n = matrix.length
    for (first <- 0 until n / 2) {
      val last = n - 1 - first
      for (i <- first until last) {
        val offset = i - first
        val top = matrix(first)(i)
        matrix(first)(i) = matrix(last - offset)(first)           // left -> top
        matrix(last - offset)(first) = matrix(last)(last - offset) // bottom -> left
        matrix(last)(last - offset) = matrix(i)(last)             // right -> bottom
        matrix(i)(last) = top                                     // top -> right
      }
    }
    matrix
  }
}

FAQ for Rust

Why does std::mem::swap(&mut matrix[i][j], &mut matrix[j][i]) not compile?

Both arguments borrow matrix mutably at the same time, and the borrow checker cannot see that they point into different rows. split_at_mut(j) splits the outer Vec into two slices that are known not to overlap, so one cell can come from each. For i32 a plain three-line swap through a temporary also works, because reading a Copy value ends the borrow.

Why take mut matrix instead of &mut Vec<Vec<i32>>?

The signature here takes the Vec by value and returns the rotated one, so the function owns it and mut on the parameter is enough to change it in place and move it back out. With a &mut Vec<Vec<i32>> signature the same loops work unchanged and nothing is returned.

Can n - 1 - first underflow?

In this debug build a usize subtraction below zero panics. The ring loop runs only for first < n / 2, so n is at least 2 there and n - 1 - first stays positive. With n = 0 the loop body never runs, so n - 1 is never computed.

Is there an iterator one-liner for transpose and reverse?

For a new matrix, yes: (0..n).map(|c| matrix.iter().rev().map(|row| row[c]).collect()).collect() reads each column bottom to top as a row, which is the clockwise turn. It allocates a new Vec per row, like the first approach.

How do I rotate counter-clockwise?

Transpose, then matrix.reverse() on the outer Vec instead of each row: that only swaps the row Vec headers, no cells move. In the copy version, cell [r][c] comes from matrix[c][n - 1 - r].

Keep going

House Robber33 / 40 · Dynamic programming · Medium

Try Rotate a Matrix in Python (Rotate a Matrix in Python), JavaScript (Rotate a Matrix in JavaScript), TypeScript (Rotate a Matrix in TypeScript), Java (Rotate a Matrix in Java), Go (Rotate a Matrix in Go), C# (Rotate a Matrix in C#), C++ (Rotate a Matrix in C++), C (Rotate a Matrix in C), Kotlin (Rotate a Matrix in Kotlin), Swift (Rotate a Matrix in Swift), PHP (Rotate a Matrix in PHP), Ruby (Rotate a Matrix in Ruby), Dart (Rotate a Matrix in Dart) or Scala (Rotate a Matrix in Scala) instead.

rotate.rs

Rust 1.98

Not run yet

+ 6 hidden

Input

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

Expected

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

The first column read bottom to top, 5, 3, 7, becomes the first row. The centre 9 stays where it is.