LeetCode 2634 – Filter Elements from Array

アルゴリズム概要

O(n)

時間計算量

O(k)

空間計算量

for loop

手法

Boolean()

truthy 評価

📌 問題要約

整数配列 arr とコールバック関数 fn を受け取り、 fn(arr[i], i) が truthy を返す要素のみの新しい配列を返す。

ただし 組み込みの Array.prototype.filter は使用禁止。

⚠️ 制約

・ 0 ≤ arr.length ≤ 1000
・ -10⁹ ≤ arr[i] ≤ 10⁹
・ Array.filter 使用禁止

📊 入出力例

Example 1

arr = [0,10,20,30] fn = (n) => n > 10

出力: [20, 30]

Example 2

arr = [1,2,3] fn = (n, i) => i === 0

出力: [1]

Example 3 — falsy 注意

arr = [-2,-1,0,1,2] fn = (n) => n + 1

出力: [-2, 0, 1, 2]

⚡ fn(-1)=0 は falsy → -1 が除外される

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

TypeScript 実装

LeetCode フォーマット準拠・strict mode 対応・外部ライブラリ不使用

type Fn = (n: number, i: number) => any;

/**
 * コールバック関数で配列をフィルタリングする
 * Array.prototype.filter の手動実装
 *
 * @param arr - フィルタ対象の整数配列
 * @param fn  - (要素値, インデックス) => truthy | falsy
 * @returns   - fn が truthy を返した要素のみの新しい配列
 *
 * @complexity Time: O(n), Space: O(k)
 *   k = フィルタ後の要素数
 */
function filter(arr: number[], fn: Fn): number[] {
  // 結果格納用の新配列（元の arr を破壊しない Pure 実装）
  const result: number[] = [];

  // インデックス i を fn に渡すため for ループを使用
  for (let i = 0; i < arr.length; i++) {
    // Boolean() で any 型の戻り値を安全に truthiness 評価
    if (Boolean(fn(arr[i], i))) {
      result.push(arr[i]);
    }
  }

  return result;
}

⚡ JavaScript の Falsy 値一覧

0 ゼロ

"" 空文字

null null

undefined 未定義

NaN 非数

false false

これ以外のすべての値（負の数・空でない文字列・空でない配列等）は truthy として扱われます。

処理フローチャート

フローの説明：
1. result を空配列で初期化する。
2. インデックス i が arr.length 未満の間、ループを継続する。
3. コールバック fn(arr[i], i) を実行し、戻り値を Boolean() で評価する。
4. truthy なら result.push(arr[i]) で追加、falsy ならスキップ。
5. i++ してループ先頭に戻る。
6. ループ終了後、result を返却する。

計算量分析

観点	計算量	説明
時間計算量	`O(n)`	全要素を1回ずつ評価
空間計算量	`O(k)`	k = フィルタ後の要素数（最悪 O(n)）
補助空間	`O(1)`	ループ変数 `i` のみ

for ループ + push

Time O(n) / Space O(k)

✅ 最もシンプル・高速
✅ インデックス直接参照可

forEach

Time O(n) / Space O(k)

✅ 使用可能（filterは禁止のみ）
⚠️ return で外部脱出不可

reduce

Time O(n) / Space O(k)

✅ 関数型スタイル
⚠️ 初学者には読みにくい