転置してから各行を逆にし、正方形の行列を時計回りに 90 度回す

数学と行列問題 145

n×n の行列を、新しい行列を作らずにその場で時計回りに 90 度回します。行と列を入れ替える転置と、各行の左右の反転の 2 つに分ければ、どちらも入れ替えだけで書ける練習です。

海外で定番の問題リスト 4 本には入っていません

問題

写真の編集の道具で、正方形の画像の画素を n×n の整数の行列 matrix で持っています。この画像を時計回りに 90 度回してください。

新しい行列を作らず、matrix をその場で書き換えてください。書き換えた matrix を返す関数にします
回したあとの i 行 j 列には、回す前の (n - 1 - j) 行 i 列の値が来ます。左の列が下から上へ読まれて、上の行になります
n は 1 以上 20 以下、値はどれも -1000 以上 1000 以下です

入力と出力の例

例 1

左の列 2、8、14 を下から読んだ 14、8、2 が、いちばん上の行になります。

matrix = [[2, 4, 6], [8, 10, 12], [14, 16, 18]]

[[14, 8, 2], [16, 10, 4], [18, 12, 6]]

例 2

2×2 では、4 つの値が 1 つずつ時計回りにずれます。

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

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

例 3

4×4 で、負の数も入っています。

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

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

面接での聞かれ方

面接では、画像の処理やゲームの盤面の話として渡されることが多いです。

「正方形の行列を 90 度回してください。追加の行列は使わないでください」
新しい行列に書き写す書き方を見せると、「その場でできますか？」と続きます
書き終えたあとに「反時計回りなら、どこを変えますか？」と聞かれることもあります

1 つの値がどこへ動くかを式で言えるか、そして動きを簡単な操作に分けられるかが見られています。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

新しい行列 out を作り、out[i][j] = matrix[n - 1 - j][i] と写せば回せます。素直で正しいですが、記憶を O(n²) 使い、その場で書き換えるという条件を満たしません。

段 2

90 度の回転は、2 つの操作に分けられます。まず転置 (i 行 j 列と j 行 i 列を入れ替える) をすると、左の列が上の行になります。ただし上から読んだ順のままです。次に各行を左右に反転すると、下から読んだ順になり、時計回りに回した形になります。

段 3

転置は、対角線より右上の値だけを、左下の相手と入れ替えます。j を i + 1 から回すのが要で、全部の組で入れ替えると 2 回入れ替わって元に戻ります。反転は、各行の両端から真ん中へ向かって入れ替えます。どちらも入れ替えだけなので、追加の記憶は要りません。

解答

Python

def rotate_matrix(matrix):
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            a = matrix[i][j]
            matrix[i][j] = matrix[j][i]
            matrix[j][i] = a
    for row in matrix:
        row.reverse()
    return matrix

JavaScript

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

Go

func rotateMatrix(
	matrix [][]int,
) [][]int {
	n := len(matrix)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			m := matrix
			m[i][j], m[j][i] =
				m[j][i], m[i][j]
		}
	}
	for _, row := range matrix {
		l, r := 0, n-1
		for l < r {
			row[l], row[r] =
				row[r], row[l]
			l++
			r--
		}
	}
	return matrix
}

Go には並びを逆にする組み込みの書き方が無いので、両端から入れ替えています。slices.Reverse を使ってもかまいません。

計算量

時間は O(n²) です。転置で約 n²/2 回、反転で約 n²/2 回入れ替えます。どの値も 1 回は動かすので、これより速くはなりません
追加の記憶は O(1) です。入れ替えに使う置き場だけです
外側の枠から 4 つの値を 1 周ずつ回す書き方でも、同じ O(n²) と O(1) になります

よくある間違い

転置で全部の組を入れ替える。 j を 0 から回すと、i 行 j 列と j 行 i 列を 2 回入れ替えて元に戻ります。対角線の右上だけを回します
反転を列でしてしまう。転置のあとに上下を反転すると、反時計回りに回った形になります。時計回りは各行の左右の反転です
新しい行列に書いて返す。答えの値は合っていても、「その場で」という条件を満たしません。面接では、条件を守れているかを先に言います
入れ替えの途中で値を上書きする。置き場を使わずに matrix[i][j] = matrix[j][i] だけを書くと、元の matrix[i][j] が消えます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def rotate_matrix(matrix: list[list[int]]) -> list[list[int]]:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(rotate_matrix([[2, 4, 6], [8, 10, 12], [14, 16, 18]]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します