行列

01 / 共通の仕組み

行列は単なる線形列ではなく、2 次元の座標空間 — 各セルは2 つの添字で指定され、 その組み合わせ方が問題ごとに異なる。要は正しい「歩き方」を見つけること。 3 つの古典的なサブパターン:その場回転(転置 + 行反転)、螺旋走査(4 つの境界が内側に収縮)、階段探索(片方向は単調増加、もう片方向は単調減少となる角から開始)。

01 / 一文での本質
右上の角から始める。現在のセルを目標と比べると、左へ動く(列全体が大きすぎる)か下へ動く(行全体が小さすぎる)かが決まる。 1 ステップで 1 行または 1 列を丸ごと除外できるので、O(R · C) ではなく O(R + C) で済む。
問題行・列ともソート済みの行列で target を探すR×C3×3target5
012012147258369j=2i=0
行列のサイズは 3×3。右上 (0, 2) から開始。目標 5。
ステップ
0 / 6
i
0
j
2
状態
探索中
0 / 6

02 / パターンの骨格

# 右上の角から開始;行も列も昇順ソート済みi ← 0; j ← C − 1while i < R and j ≥ 0:if mat[i][j] == target: return (i, j)elif mat[i][j] > target: j ← j − 1 # 列ごと除外else: i ← i + 1 # 行ごと除外return (−1, −1) # 範囲外に出た

03 / このパターンを使うべき合図

「行も列も昇順にソート済み」
LC 240 —— Search a 2-D Matrix II の典型用法。各行は左から右へ、各列は上から下へ昇順、 ただし行末と次行頭の大小関係は保証されない。この設定では階段探索が正解、二分探索ではない。
「各行ソート済み、次行先頭 > 前行末尾」
LC 74 —— 似ているがそっくりさんの罠。行末から次行頭への大小関係が追加されると、 行列全体が 1 本のソート列に化けるので、R · C 個のインデックスへ二分するのが正解、O(log(R · C)) で階段より速い。次元ではなくソート構造を見る。
「ソート済み行列の k 番目に小さい値」
LC 378 —— 同じ行列単調構造で、聞いていることが存在ではなく順位。 階段歩きは一般化できる:角から O(R + C) で x 以下のセル数を数え、x を二分すればよい。
「ソート済み格子で性質を満たす対の数を数える」
一方向が値を単調増加させ、もう一方向が単調減少させる二次元格子なら、 1 回の階段歩きで関係する全ての境界セルを訪問できる。 ソート済み配列で A[i] + B[j] < T を満たす対 (i, j) を数えるのも同じ形。

04 / よくある落とし穴

i.
左上または右下の角から始めてしまう。
これらの角は行列全体の最小値・最大値で、2 つの隣接セルはどちらも同方向に動く(両方とも大きい、両方とも小さい)—— 1 回の比較ではどちらの軸へ後退すべきか分からない。 階段が成立するのは、右上と左下の「片方が大きく、片方が小さい」性質をもつ角のみ。
ii.
LC 74(行折り返しソート)と LC 240(行列独立にソート)を混同する。
LC 74 は各行の先頭が前行末より大きいと保証する —— 行列全体が 1 本のソート列に潰れ、 正しい道具は R · C 要素への二分。LC 240 は行と列が独立にソートとしか言わず、 行末と次行頭の関係は何も約束しない —— その弱さが階段探索を強いる。図ではなく制約を読むこと。
iii.
i == R または j < 0 でのループ境界を忘れる。
上端または右端を越えた時点で目標は行列内には存在しないので、(−1, −1)(または false)を返す。片側だけ調べたり列インデックスを 1 つずらしたりすると、 最後の列の答えを取り逃すか範囲外アクセスでクラッシュする。i < R と j ≥ 0 の両方を毎反復で守る。

05 / LeetCode で練習

4 問。1 問目は教科書的な階段歩き、2 問目は「似ているが二分が正解」の罠、 残り 2 問は同じ行列単調構造を順位付け・カウントに転用する。

01Search a 2-D Matrix II— LC 240中級→02Search a 2-D Matrix— LC 74中級→03Kth Smallest Element in a Sorted Matrix— LC 378中級→04Kth Smallest Number in Multiplication Table— LC 668難しい→

— / どれをいつ使うか

その場回転
グリッド自体の幾何変換 — 90° / 180° 回転、転置、鏡像 — を行う問題で使う。 2 段(転置 + 行反転)に分解すれば追加グリッド無しでその場処理できる。
転置 + 反転 · LC 48
螺旋走査
縮小していく矩形の外周沿いに全セルを訪問する必要があるとき — 螺旋出力、螺旋充填、層カウント。 4 つの境界を保持し、1 周ごとに内側へ収縮させる。
4 つの境界 · LC 54 · LC 59
階段探索
行と列の両方向で単調な行列で、値を探すときに使う。 片方向が厳密に増加、もう片方向が厳密に減少する角から始めれば、 1 回の比較で 1 行または 1 列を丸ごと除外できる。
右上角から · LC 240 · O(N + M)