【JavaScript】最大1つの0を反転して作れる「1」の最長連続数を求めるアルゴリズム

問題

0と1のみで構成されるバイナリ配列 arr を唯一の引数として受け取るJavaScript関数を作成する必要があります。この関数は、「最大で1つの0を1に反転できる」という条件下で、配列中に現れる連続する1の最大数を求めて返します。

たとえば、関数への入力が次の場合を考えてみましょう。

const arr = [1, 0, 1, 1, 0];

このとき、期待される出力は次のとおりです。

const output = 4;

出力の説明

配列のインデックス1にある0を反転すると、[1, 1, 1, 1, 0] となり、先頭から4つ連続した1が得られます。これより長い連続は作れないため、答えは4となります。

アプローチ:スライディングウィンドウ(2ポインタ)法

この問題は、スライディングウィンドウの考え方を使うと効率的に解けます。2つのポインタ i(左端)と j(右端)でウィンドウを管理し、ウィンドウ内に含まれる0の個数が常に1個以内になるよう制御するのがポイントです。処理の流れは以下のとおりです。

• j を右端として配列を先頭から順に走査します。
• nums[j] が1の場合は、現在のウィンドウの幅(j - i + 1)で答え res を更新します。
• nums[j] が0の場合は0のカウントを増やします。カウントが2になったら、直前に見つかった0の位置(first)の次へ左端 i を移動させ、ウィンドウ内の0の個数を再び1個に戻します。

この手法により、配列を一度だけ走査するだけでよく、時間計算量はO(n)、空間計算量はO(1)という非常に効率的な実装になります。

実装例

実際のコードは次のとおりです。

const arr = [1, 0, 1, 1, 0];
const findMaximumOne = (nums = []) => {
    let count = 0;
    let first = -1;
    let i = 0, j = 0;
    let res = -Infinity;
    while (j < nums.length) {
        if (nums[j] === 1) {
            res = Math.max(res, j - i + 1);
        } else {
            count++;
            if (count == 2) {
                i = first + 1;
                count--;
            }
            first = j;
        }
        j++;
    }
    return res;
};
console.log(findMaximumOne(arr));

コードの解説

• count:現在のウィンドウ内に含まれる0の個数を追跡します。
• first:ウィンドウ内に存在する直近の0のインデックスを記録しておき、0が2個になった際に左端を移動させる基準として使います。
• res:これまでに見つかった連続する1の最大長を保持します。

出力

上記のコードをコンソールで実行すると、次の結果が出力されます。

4