🌀 Spiral Matrix Algorithm

TypeScript実装の詳細解析と可視化

📝 完全なソースコード

spiralMatrix.ts 
/**
 * 行列を螺旋状の順序で読み取り、要素を配列として返す
 * @param matrix - m x n の整数行列
 * @returns 螺旋状に読み取った要素の配列
 */
function spiralOrder(matrix: number[][]): number[] {
    // 空の行列チェック
    if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
        return [];
    }
    
    const m = matrix.length;
    const n = matrix[0].length;
    const result: number[] = [];
    
    // 境界を定義
    let top = 0;
    let bottom = m - 1;
    let left = 0;
    let right = n - 1;
    
    while (top <= bottom && left <= right) {
        // 上の行を左から右へ
        for (let j = left; j <= right; j++) {
            result.push(matrix[top][j]);
        }
        top++;
        
        // 右の列を上から下へ
        for (let i = top; i <= bottom; i++) {
            result.push(matrix[i][right]);
        }
        right--;
        
        // 下の行を右から左へ（残りの行がある場合）
        if (top <= bottom) {
            for (let j = right; j >= left; j--) {
                result.push(matrix[bottom][j]);
            }
            bottom--;
        }
        
        // 左の列を下から上へ（残りの列がある場合）
        if (left <= right) {
            for (let i = bottom; i >= top; i--) {
                result.push(matrix[i][left]);
            }
            left++;
        }
    }
    
    return result;
}

🎯 アルゴリズムの可視化

Example 1: 3×3 行列

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

Example 2: 3×4 行列

1
2
3
4
5
6
7
8
9
10
11
12
→
[1,2,3,4,8,12,11,10,9,5,6,7]

🔍 ステップバイステップ解析

1初期化と境界設定

初期化処理
const m = matrix.length;        // 行数
const n = matrix[0].length;     // 列数
const result: number[] = [];    // 結果配列

// 4つの境界を設定
let top = 0;        // 上境界
let bottom = m - 1; // 下境界  
let left = 0;       // 左境界
let right = n - 1;  // 右境界

4つの境界変数を使って、現在処理中の範囲を管理します。これらの境界は処理が進むにつれて内側に移動します。

2右方向への移動

上の行を左から右へ
for (let j = left; j <= right; j++) {
    result.push(matrix[top][j]);
}
top++; // 上境界を1行下に移動

最上行を左から右に読み取り、処理後に上境界を1行下に移動します。

3下方向への移動

右の列を上から下へ
for (let i = top; i <= bottom; i++) {
    result.push(matrix[i][right]);
}
right--; // 右境界を1列左に移動

最右列を上から下に読み取り、処理後に右境界を1列左に移動します。

4左方向への移動

下の行を右から左へ
if (top <= bottom) {
    for (let j = right; j >= left; j--) {
        result.push(matrix[bottom][j]);
    }
    bottom--; // 下境界を1行上に移動
}

最下行を右から左に読み取ります。残りの行がある場合のみ実行し、処理後に下境界を1行上に移動します。

5上方向への移動

左の列を下から上へ
if (left <= right) {
    for (let i = bottom; i >= top; i--) {
        result.push(matrix[i][left]);
    }
    left++; // 左境界を1列右に移動
}

最左列を下から上に読み取ります。残りの列がある場合のみ実行し、処理後に左境界を1列右に移動します。

⚡ 計算量解析

🕐 時間計算量: O(m × n)

各要素を正確に1回だけ訪問するため、行列のサイズに線形比例します。

💾 空間計算量: O(1)

結果配列以外に使用する追加メモリは境界変数（top, bottom, left, right）のみで、定数量です。

🎨 重要なポイント

境界条件のチェック

下方向と左方向の移動では、重複処理を避けるために境界条件をチェックしています。これにより、単一行や単一列の行列でも正しく動作します。

効率的な境界管理

4つの境界変数を使用することで、複雑な座標計算を避け、シンプルで理解しやすいコードを実現しています。

TypeScript の型安全性

明示的な型注釈により、コンパイル時の型チェックが可能で、実行時エラーを防ぎます。