Flatten Deeply Nested Array

アルゴリズム概要

問題定義

多次元配列 arr と深さ n を受け取り、指定された深さまで平坦化した配列を返します。平坦化は現在のネスト深度が n 未満の場合にのみ実行されます。最初の配列の要素は深度 0 とみなされます。

入出力例

入力: arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]], n = 0
出力: [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
説明: n=0 の場合、平坦化されません

入力: arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]], n = 1
出力: [1, 2, 3, 4, 5, 6, 7, 8, [9, 10, 11], 12, 13, 14, 15]
説明: 深度0のサブ配列のみ平坦化されます

制約条件

• 配列内の数値の数: 0 ≤ count ≤ 10⁵
• サブ配列の数: 0 ≤ count ≤ 10⁵
• 最大深度 maxDepth ≤ 1000
• 各数値: -1000 ≤ number ≤ 1000
• 平坦化深度: 0 ≤ n ≤ 1000
• Array.flat の使用は禁止

アルゴリズム戦略

性能

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

TypeScript実装

type MultiDimensionalArray = (number | MultiDimensionalArray)[];

/**
 * 多次元配列を指定された深さまで平坦化する
 *
 * @param arr - 平坦化する多次元配列
 * @param n - 平坦化する深さ（0の場合は平坦化しない）
 * @returns 平坦化された配列
 *
 * @complexity
 * Time: O(N) - N は全要素数
 * Space: O(N + D) - N は結果配列、D はコールスタック深度
 *
 * @example
 * flat([1, 2, [3, 4]], 1) // [1, 2, 3, 4]
 * flat([1, [2, [3]]], 1) // [1, 2, [3]]
 */
var flat = function (arr: MultiDimensionalArray, n: number): MultiDimensionalArray {
    // 結果配列を初期化（クロージャで共有）
    const result: MultiDimensionalArray = [];

    /**
     * 内部再帰関数：配列を深さ制限付きで平坦化
     * @param items - 処理対象の配列
     * @param depth - 残りの平坦化可能深度
     */
    function flatten(items: MultiDimensionalArray, depth: number): void {
        for (const item of items) {
            // 配列かつ深度制限内の場合、再帰的に展開
            if (Array.isArray(item) && depth > 0) {
                flatten(item, depth - 1);
            } else {
                // プリミティブまたは深度制限到達の配列をそのまま追加
                result.push(item);
            }
        }
    }

    // 初期呼び出し
    flatten(arr, n);

    return result;
};

実装のポイント

フローチャート

計算量分析

アプローチ比較