Pascal's Triangle II

アルゴリズム概要

ステップバイステップ解説

代表例 rowIndex = 4 を使って、 配列 row がどのように埋まっていくかを1ステップずつ追跡します。

Python実装

from __future__ import annotations

from typing import List


class Solution:
    """
    119. Pascal's Triangle II を解決するクラス

    パスカルの三角形の rowIndex 行目を、二項係数の漸化式を使って
    O(rowIndex) 時間・O(rowIndex) 追加空間で求める。
    """

    def getRow(self, rowIndex: int) -> List[int]:
        """
        パスカルの三角形の rowIndex 行目（0-indexed）を返す

        Args:
            rowIndex: 求めたい行番号（0 <= rowIndex <= 33）

        Returns:
            rowIndex 行目の値を格納したリスト

        Raises:
            TypeError: rowIndex が int 型でない場合
            ValueError: rowIndex が 0〜33 の範囲外の場合
        """
        # 型ヒントは実行時には無視される。呼び出し元が誤った型を渡した場合に
        # 実行時までエラーに気づけないため、isinstance() で別途検証する。
        self._validate_input(rowIndex)

        # 結果を格納するリストを先に確保する。
        # フォローアップの「O(rowIndex)の追加空間」を満たすため、
        # 過去の行を丸ごと保持する二次元リストは作らず、この1本のリストだけを使い回す。
        row: List[int] = [0] * (rowIndex + 1)

        # パスカルの三角形の左端は、どの行でも必ず1になる
        # （rowIndex個からk=0個を選ぶ組み合わせは「何も選ばない」の1通りしかないため）
        row[0] = 1

        # 二項係数の漸化式 C(n, k) = C(n, k-1) * (n - k + 1) // k を使い、
        # 1つ左の値から次の値を順番に計算していく（同じ行の中だけで完結する）
        for k in range(1, rowIndex + 1):
            # 掛け算を先に行ってから割り算をする。
            # 「//」（フロア除算）を使うのは、Pythonの「/」が常にfloatを返してしまい
            # List[int]という戻り値の型と食い違ってしまうため。
            # 二項係数は必ず整数になる値なので、掛け算を先に行えば割り切れずに誤差が出ることはない。
            row[k] = row[k - 1] * (rowIndex - k + 1) // k

        return row

    def _validate_input(self, row_index: int) -> None:
        """入力値が問題の制約を満たすかを検証する"""
        # isinstance() で型チェックする。
        # bool は int のサブクラスなので、isinstance(True, int) は True になってしまう。
        # そのため True/False が誤って渡されるケースも別途弾いておく。
        if not isinstance(row_index, int) or isinstance(row_index, bool):
            raise TypeError("rowIndex must be an int")

        if not (0 <= row_index <= 33):
            raise ValueError("rowIndex must be between 0 and 33")

呼び出し: Solution().getRow(3)
Step 1: _validate_input(3) → isinstance(3, int)かつboolではない → OK、0<=3<=33 → OK
Step 2: row = [0, 0, 0, 0] を確保 → row[0] = 1 → row = [1, 0, 0, 0]
Step 3: k=1 → row[1] = row[0] * (3-1+1) // 1 = 1 * 3 // 1 = 3 → row = [1, 3, 0, 0]
Step 4: k=2 → row[2] = row[1] * (3-2+1) // 2 = 3 * 2 // 2 = 3 → row = [1, 3, 3, 0]
Step 5: k=3 → row[3] = row[2] * (3-3+1) // 3 = 3 * 1 // 3 = 1 → row = [1, 3, 3, 1]
最終結果: [1, 3, 3, 1]（Example 1の出力と一致）

処理フローチャート

フローの説明：
このアルゴリズムには「行を積み上げるループ」が存在しません。緑の矢印で示した通り、 入力検証を通過した後は「配列の確保」「基底値の設定」を1回ずつ行い、 あとは紫のループバック矢印が示す通り k を 1つずつ増やしながら同じ行の中だけを計算し続けます。ループが二重になっていない点が、 三角形全体を作る方法との決定的な違いです。

計算量分析

📖 用語集

このページで登場した専門用語をまとめました。分からない言葉が出てきたときに参照してください（五十音順）。