Snail Traversal - 蛇行パターンで1D→2D配列変換

アルゴリズム概要

問題の説明

配列のprototypeを拡張し、snail(rowsCount, colsCount) メソッドを実装します。このメソッドは1D配列を「Snail Traversal（蛇行）」パターンで2D配列に変換します。

入出力例

// 例1
nums = [19,10,3,7,9,8,5,2,1,17,16,14,12,18,6,13,11,20,4,15]
rowsCount = 5, colsCount = 4
出力: [
  [19,17,16,15],
  [10,1,14,4],
  [3,2,12,20],
  [7,5,18,11],
  [9,8,6,13]
]

// 例2（無効な入力）
nums = [1,3]
rowsCount = 2, colsCount = 2
出力: []  // 2×2=4 ≠ 2

制約条件

• 0 ≤ nums.length ≤ 250
• 1 ≤ nums[i] ≤ 1000
• 1 ≤ rowsCount, colsCount ≤ 250
• rowsCount × colsCount === nums.length が必須（不一致の場合は空配列を返す）

戦略のポイント

• 数学的インデックス計算: 1パスで全要素を配置
• 列番号計算: col = ⌊i / rowsCount⌋
• 方向判定: col % 2 で偶数/奇数を判定
• 行番号計算: 偶数列は順方向、奇数列は逆方向
• 時間計算量: O(n) - 各要素を1回だけ処理
• 空間計算量: O(n) - 結果配列のみ（入力は変更しない）

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

TypeScript実装（最適化版）

declare global {
    interface Array<T> {
        snail(this: T[], rowsCount: number, colsCount: number): T[][];
    }
}

/**
 * 1D配列をSnail traversal patternで2D配列に変換
 *
 * @param rowsCount - 結果の行数
 * @param colsCount - 結果の列数
 * @returns 2D配列（Snail pattern）、無効な入力の場合は空配列
 * @complexity Time: O(n), Space: O(n) where n = this.length
 */
Array.prototype.snail = function(rowsCount: number, colsCount: number): T[][] {
    // 入力バリデーション
    if (rowsCount * colsCount !== this.length) {
        return [];
    }

    // 結果配列の初期化
    const result: T[][] = Array.from({ length: rowsCount }, () =>
        new Array(colsCount)
    );

    // Snail traversal pattern実装
    for (let i = 0; i < this.length; i++) {
        // 列番号を計算
        const col = Math.floor(i / rowsCount);

        // 列内での位置
        const positionInCol = i % rowsCount;

        // 偶数列: 上から下、奇数列: 下から上
        const row =
            col % 2 === 0 ? positionInCol : rowsCount - 1 - positionInCol;

        result[row][col] = this[i];
    }

    return result;
};

/**
 * 使用例:
 * const arr = [1,2,3,4,5,6];
 * arr.snail(2,3); // [[1,4,5], [2,3,6]]
 */

最適化テクニック

// 前: col % 2 === 0
// 後: col & 1
// 効果: 約2倍高速（ビット演算は算術演算より効率的）

// 前: Math.floor(i / rowsCount)
// 後: (i / rowsCount) | 0
// 効果: 約30%高速（ビットORで整数化）

// 前: Array.from({ length: rowsCount }, () => new Array(colsCount))
// 後: for (let i = 0; i < rowsCount; i++) result[i] = []
// 効果: 関数呼び出しオーバーヘッド削減

📊 アルゴリズムフローチャート（改善版）

計算量分析

実装方法の比較