JavaScriptでソートすべき最短の部分配列の長さを求める方法

問題

数値の配列 arr を最初の（そして唯一の）引数として受け取るJavaScript関数を作成する必要があります。

この関数の目的は、ある連続した部分配列を見つけ、その部分配列だけを昇順にソートしたときに、配列全体が昇順にソートされた状態になるようにする、その部分配列の長さを求めることです。

例えば、関数への入力が以下の場合を考えてみましょう。

const arr = [3, 7, 5, 9, 11, 10, 16];

このとき、出力は次のようになります。

const output = 5;

出力の説明

[7, 5, 9, 11, 10] の部分配列だけをソートすると、配列全体が昇順に並び替えられるためです。

解決のアプローチ：ソート済み配列との比較

この問題を解く最もシンプルで直感的な方法は、元の配列のコピーを作成してソートし、元の配列と要素を順番に比較することです。

具体的な手順は以下の通りです。

1. 元の配列をコピーし、昇順にソートした配列を作成します。
2. 先頭から順に元の配列とソート済み配列を比較し、最初に値が異なる位置（start）を見つけます。
3. 末尾から順に同様の比較を行い、最後に値が異なる位置（end）を見つけます。
4. start から end までの要素数（end - start + 1）が答えとなります。配列がすでにソート済みの場合は 0 を返します。

コード例

以下が実際のコードです。

const arr = [3, 7, 5, 9, 11, 10, 16];
const shortestLength = (arr = []) => {
   const sorted = [...arr].sort((a, b) => a - b)
   let start = 0
   let end = sorted.length - 1
   while (sorted[start] === arr[start] && start < arr.length) {
      start += 1
   }
   while (sorted[end] === arr[end] && end >= 0) {
      end -= 1
   }
   return end >= start ? end - start + 1 : 0
}
console.log(shortestLength(arr));

出力

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

5

計算量について

このアプローチの時間計算量は O(n log n)（配列のソートに依存）、空間計算量は O(n)（配列のコピーが必要なため）です。配列がすでにソートされている場合でも、whileループによる走査は O(n) で完了するため、全体として効率的な解法と言えます。