【JavaScript】配列から1要素の削除で「厳密に増加する数列」を作れるか判定する方法

整数の数列が配列として与えられたとき、そこから最大で1つの要素を削除することによって、厳密に増加する数列(strictly increasing sequence)を作ることができるかどうかを判定する問題について解説します。

問題の例

例を見てみましょう。

• sequence = [1, 3, 2, 1] の場合 → 出力は false。この配列では、どの1要素を取り除いても厳密に増加する数列を得ることはできません。
• sequence = [1, 3, 2] の場合 → 出力は true。「3」を削除すれば [1, 2] という厳密に増加する数列が得られます。あるいは「2」を削除して [1, 3] としても構いません。

「厳密に増加する数列」とは

これは数学用語の一つで、隣り合うすべての要素において、後ろの要素が前の要素よりも必ず大きいような数列の並びを指します。

これに対して、単なる「増加数列(increasing sequence)」では、後ろの要素が前の要素以上(等しい場合も含む)であればよいとされます。減少数列や厳密に減少する数列についても同様の考え方が適用できます。

アプローチ

配列を先頭から順にループし、「次の要素が前の要素より大きいか」どうかをチェックしていきます。

• 大きければ問題なし。そのまま次へ進みます。
• 大きくなければ(ここでは「以上」ではなく「より大きい」が必要な点に注意してください)、問題のある要素としてカウント unwantedElements を +1 します。

反復処理の途中でカウントが 1 を超えた時点で、即座に false を返します。逆に、最後まで処理を完了したときに unwantedElements <= 1 であれば true を返せばよいわけです。

サンプルコード

それでは、この関数のコードを書いてみましょう。

const isStrictlyIncreasing = (arr) => {
   let unwantedElements = 0;
   for(let i = 0; i < arr.length - 1; i++){
      if(arr[i] >= arr[i+1]){
         unwantedElements++;
         if(unwantedElements > 1){
            return false;
         };
      };
   };
   return true;
};
console.log(isStrictlyIncreasing([1, 3, 2, 1]));
console.log(isStrictlyIncreasing([1, 3, 2]));

実行結果

コンソールには以下のように出力されます。

false
true

まとめ

このアルゴリズムは配列を一度だけ走査すればよいため、計算量は O(n) と効率的です。単純なカウンタを使うだけで、要素の削除を実際に行わずに判定できるのがポイントです。