4 つの境目を狭めながら、行列を渦巻きの順に読む

m×n の行列を、左上から時計回りに外側の枠から内側へ渦巻きの順に読んだ並びを返します。上、下、左、右の 4 つの境目を持ち、1 辺を読むたびに 1 つ狭める練習です。

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

問題

倉庫の棚の区画が、m 行 n 列の整数の行列 matrix で表されています。見回りのロボットは左上の区画から出発し、右へ進み、端に着いたら下へ、次に左へ、次に上へと、時計回りに曲がりながら、まだ通っていない区画だけを通って内側へ進みます。ロボットが通った順に区画の値を並べて返す関数を書いてください。

どの区画もちょうど 1 回ずつ通ります。答えの長さは m × n です
m と n はどちらも 1 以上 10 以下、値はどれも -100 以上 100 以下です

入力と出力の例

例 1

外側の枠を 1 周したあと、内側の 21 と 22 を読みます。

matrix = [[10, 11, 12, 13], [20, 21, 22, 23], [30, 31, 32, 33]]

[10, 11, 12, 13, 23, 33, 32, 31, 30, 20, 21, 22]

例 2

1 列だけなら、上から下へ読んで終わりです。

matrix = [[4], [5], [6]]

[4, 5, 6]

例 3

縦に長い 4 行 2 列です。右へ 1 歩、下へ、左へ 1 歩、上へと 1 周で全部を通ります。

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

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

面接での聞かれ方

面接では、行列の扱いに慣れているかを見る問題として出されます。

「行列を渦巻きの順で返してください」
正方形の例で説明されたあと、「行と列の数が違うときも動きますか？」と確かめられます
書き終えたあとに「1 行だけ、1 列だけのときをたどってください」と言われることがあります

考え方は難しくありませんが、境目の数え間違いで同じ区画を 2 回読みやすい問題です。端の場合を自分で確かめられるかが見られています。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

通った区画に印を付け、進む向きを右、下、左、上の順に回して、次が端か印付きなら曲がる書き方もあります。正しく動きますが、印のための m × n の記憶が要ります。

段 2

まだ読んでいない区画は、いつも長方形のまとまりになっています。そこで、その長方形の上の行 top、下の行 bottom、左の列 left、右の列 right の 4 つだけを持ちます。

段 3

1 周を 4 つの辺に分けます。上の行を左から右へ読んだら top を 1 つ下げ、右の列を上から下へ読んだら right を 1 つ左へ、下の行を右から左へ読んだら bottom を 1 つ上げ、左の列を下から上へ読んだら left を 1 つ右へ寄せます。

段 4

下の行と左の列を読む前に、まだ残っているかを確かめます。例 2 のように 1 列だけ残ると、右の列を読み終えた時点で left > right になっています。ここで確かめないと、同じ区画を逆向きにもう一度読んでしまいます。

解答

Python

def spiral_order(matrix):
    top = 0
    bottom = len(matrix) - 1
    left = 0
    right = len(matrix[0]) - 1
    out = []
    while top <= bottom and left <= right:
        for j in range(left, right + 1):
            out.append(matrix[top][j])
        top += 1
        for i in range(top, bottom + 1):
            out.append(matrix[i][right])
        right -= 1
        if top <= bottom:
            for j in range(
                right, left - 1, -1
            ):
                out.append(matrix[bottom][j])
            bottom -= 1
        if left <= right:
            for i in range(
                bottom, top - 1, -1
            ):
                out.append(matrix[i][left])
            left += 1
    return out

JavaScript

function spiralOrder(matrix) {
  let top = 0;
  let bottom = matrix.length - 1;
  let left = 0;
  let right = matrix[0].length - 1;
  const out = [];
  while (
    top <= bottom &&
    left <= right
  ) {
    for (let j = left; j <= right; j++) {
      out.push(matrix[top][j]);
    }
    top++;
    for (let i = top; i <= bottom; i++) {
      out.push(matrix[i][right]);
    }
    right--;
    if (top <= bottom) {
      for (let j = right; j >= left; j--) {
        out.push(matrix[bottom][j]);
      }
      bottom--;
    }
    if (left <= right) {
      for (let i = bottom; i >= top; i--) {
        out.push(matrix[i][left]);
      }
      left++;
    }
  }
  return out;
}

Go

func spiralOrder(
	matrix [][]int,
) []int {
	top, bottom := 0, len(matrix)-1
	left := 0
	right := len(matrix[0]) - 1
	out := []int{}
	for top <= bottom && left <= right {
		for j := left; j <= right; j++ {
			out = append(out, matrix[top][j])
		}
		top++
		for i := top; i <= bottom; i++ {
			out = append(out, matrix[i][right])
		}
		right--
		if top <= bottom {
			for j := right; j >= left; j-- {
				v := matrix[bottom][j]
				out = append(out, v)
			}
			bottom--
		}
		if left <= right {
			for i := bottom; i >= top; i-- {
				out = append(out, matrix[i][left])
			}
			left++
		}
	}
	return out
}

上の行と右の列は、ループの条件が守っているので確かめは要りません。下の行と左の列だけ、読む前に確かめます。

計算量

時間は O(m × n) です。どの区画も 1 回ずつ読みます
追加の記憶は、答えの並びを除けば O(1) です。4 つの境目だけを持ちます
印を付ける書き方は、時間は同じですが、印の分の O(m × n) の記憶が要ります

よくある間違い

下の行と左の列の前に確かめない。例 2 では、右の列を読み終えたあと left > right なので、確かめずに左の列を下から上へ読むと、5 をもう一度足してしまいます。1 行だけ残った場合も、下の行で同じことが起きます
境目を狭める順を間違える。上の行を読んだあとに top を下げずに右の列を読むと、右上の角を 2 回読みます。1 辺読んだらすぐ狭めます
正方形だけで確かめる。正方形では偶然うまくいく書き方でも、例 1 や例 3 のような長方形で外れることがあります。縦長、横長、1 行、1 列で手を動かして確かめます

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

main.py

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

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

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

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


# 「実行」を押すと、この行の結果が出ます
print(spiral_order([[10, 11, 12, 13], [20, 21, 22, 23], [30, 31, 32, 33]]))

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