先頭の
行列の
海外で定番の問題リスト 4 本には入っていません
問題
表計算のmatrix をmatrix の 0 だけで
- 新しい
行列を 作らず、 matrixをその場で 書き換えてください。 書き換えた matrixを返す関数にします - 追加の
記憶は O(1) を 目指してください - m と n は
どちらも 1 以上 200 以下、 値は どれも -2147483648 以上 2147483647 以下です
入力と出力の例
例 1
0 は 1 行 2 列に
例 2
先頭の
例 3
0 が 2 つ
面接での聞かれ方
面接では、
- 「0 が
ある 行と 列を 全部 0 に してください。 その 場で 書き換えてください」 - 0 の
行と 列を 集合に 覚える 書き方を 見せると、 「追加の 記憶を O(1) に できますか？」と続きます - 「見つけた
その 場で 0 に したら どうなりますか？」と、 まずい 書き方の 理由を 聞かれる こともあります
印を
ヒント
まだ開いていません
付箋は 4 枚。下の段ほど答えに近づきます
ヒント 2
ヒント 3
ヒント 4答えに近い
アルゴリズムのチートシートの「配列と文字列」に、
関わる学び
配列と
まず
段 1
0 を
段 2
消す行の
段 3
印のmatrix[i][0] と、matrix[0][j] を 0 にします。matrix[0][0] は 0 行目と 0 列目のcol0 で
段 4
書き換えは、col0 が
解答
Python
Python
def zero_matrix(matrix):
m = len(matrix)
n = len(matrix[0])
col0 = False
for i in range(m):
row = matrix[i]
if row[0] == 0:
col0 = True
for j in range(1, n):
if row[j] == 0:
row[0] = 0
matrix[0][j] = 0
for i in range(m - 1, -1, -1):
row = matrix[i]
for j in range(n - 1, 0, -1):
if (
row[0] == 0
or matrix[0][j] == 0
):
row[j] = 0
if col0:
row[0] = 0
return matrixJavaScript
JavaScript
function zeroMatrix(matrix) {
const m = matrix.length;
const n = matrix[0].length;
const head = matrix[0];
let col0 = false;
for (let i = 0; i < m; i++) {
const row = matrix[i];
if (row[0] === 0) {
col0 = true;
}
for (let j = 1; j < n; j++) {
if (row[j] === 0) {
row[0] = 0;
head[j] = 0;
}
}
}
for (let i = m - 1; i >= 0; i--) {
const row = matrix[i];
for (let j = n - 1; j > 0; j--) {
if (
row[0] === 0 ||
head[j] === 0
) {
row[j] = 0;
}
}
if (col0) {
row[0] = 0;
}
}
return matrix;
}Go
Go
func zeroMatrix(
matrix [][]int,
) [][]int {
m, n := len(matrix), len(matrix[0])
head := matrix[0]
col0 := false
for _, row := range matrix {
if row[0] == 0 {
col0 = true
}
for j := 1; j < n; j++ {
if row[j] == 0 {
row[0] = 0
head[j] = 0
}
}
}
for i := m - 1; i >= 0; i-- {
row := matrix[i]
for j := n - 1; j > 0; j-- {
if row[0] == 0 ||
head[j] == 0 {
row[j] = 0
}
}
if col0 {
row[0] = 0
}
}
return matrix
}head は 0 行目head[j] = 0 は matrix[0][j] を
計算量
- 時間は O(m × n) です。
行列を 2 回なめます - 追加の
記憶は O(1) です。 印は 行列の 先頭の 行と 列に 書き、 ほかには col0だけを持ちます - 集合に
覚える 書き方は、 時間は 同じで、 記憶が O(m + n) に なります。 面接では まずこちらを 言い、 そこから 詰めると 話が 伝わりやすくなります
よく
- 見つけた
その 場で 0 にする。 例 1 で 1 行目を 0 に すると、 次に 見る 1 行目の 0 が また行と 列を 消し、 どんどん 広がります - 0 行目と 0 列目の
印を matrix[0][0]1 つで兼ねる。matrix[0][0]が 0 のとき、 0 行目を 消すのか、 0 列目を 消すのか、 両方なのかが 分かりません。 0 列目の 分は col0に分けます - 左上から
書き換える。 先に 0 行目や 0 列目を 書き換えると、 まだ 使っていない 印が 全部 0 に 見え、 例 1 で 行列全部が 0 に なります。 右下から戻ります col0を見る ループを 1 行目から始める。 0 行目の 先頭の 0 を 見落として col0が立たず、 例 2 で 1 行目の 先頭の 1 が 0 に なりません
解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日
面接での
書き始める
「消す行と
列を 集合に 覚えれば O(m + n) の 記憶で 解けます。 O(1) に する ために、 印を 行列の 先頭の 行と 列に 書きます。 0 列目に 0 が あったかだけは 左上と 兼ねられないので、 真偽の 値で 別に 持ちます。 書き換えは、 印を 先に 消さないよう右下から 進めます。 時間は O(m × n) です。」
書き終えたら、
「例 1 を
たどります。 1 行 2 列の 0 を 見て、 1 行目の 先頭と 2 列目の 先頭を 0 にします。 0 列目に 0 は 無いので col0は偽です。 右下から 戻ると、 2 列目は 全部 0 に、 1 行目も 全部 0 に なり、 [[3, 8, 0], [0, 0, 0], [5, 7, 0]]です。」