JavaScriptで2つの配列を厳密に増加させるための最小スワップ回数を求める方法

厳密に増加する数列とは

数列が厳密に増加する（strictly increasing）とは、arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1] という条件が成り立つことを指します。つまり、隣り合うどの要素を見ても、必ず右側の要素が左側の要素より大きくなければならないということです。

問題の概要

2つの数値配列 arr1 と arr2 を引数として受け取るJavaScript関数を実装します（第一引数が arr1、第二引数が arr2 です）。

この操作では、同じインデックス位置にある要素同士のみを入れ替えることができます。つまり、arr1[i] と arr2[i] をスワップするということです。この操作は何度行っても構いません。その上で、両方の配列を同時に厳密に増加する数列へと変形するために必要な最小スワップ回数を関数の戻り値として返します。

たとえば、関数への入力が次のようなケースを考えてみましょう。

入力

const arr1 = [1, 3, 5, 4];
const arr2 = [1, 2, 3, 7];

出力

const output = 1;

出力の解説

arr1[3] の「4」と arr2[3] の「7」を一度だけ入れ替えると、arr1 は [1, 3, 5, 7]、arr2 は [1, 2, 3, 4] となり、どちらも厳密に増加する数列になります。これより少ないスワップ回数で条件を満たすことはできないため、答えは 1 です。

解法の考え方：動的計画法（DP）

各インデックスについて「その位置でスワップした場合」と「しなかった場合」という2通りの状態を想定し、それぞれの状態に到達するまでの最小スワップ回数を順番に更新していくのがポイントです。

インデックス i における遷移は、次の2つの条件で判断できます。

• 交差スワップが有効な場合：arr1[i] > arr2[i - 1] かつ arr2[i] > arr1[i - 1] が成り立つとき、前の位置と反対の状態（前でスワップなし→今回はスワップあり、またはその逆）へ遷移できます。
• そのまま維持できる場合：arr1[i] > arr1[i - 1] かつ arr2[i] > arr2[i - 1] が成り立つとき、前の位置と同じ状態（両方ともスワップなし、または両方ともスワップあり）を保ったまま遷移できます。

サンプルコード

以下が実際の実装例です。

const arr1 = [1, 3, 5, 4];
const arr2 = [1, 2, 3, 7];

const findSwaps = (arr1 = [], arr2 = []) => {
    // 直前の位置での状態別の最小コストを保持
    // true: スワップした場合 / false: スワップしなかった場合
    let map = {
        true: 1,
        false: 0,
    };
    for (let i = 1; i < arr1.length; i++) {
        const current = {
            true: Infinity,
            false: Infinity,
        };
        // 交差スワップで遷移できる場合
        if (arr1[i] > arr2[i - 1] && arr2[i] > arr1[i - 1]) {
            current.true = Math.min(
                current.true,
                map.false + 1,
            );
            current.false = Math.min(
                current.false,
                map.true,
            );
        }
        // 同じ状態を維持して遷移できる場合
        if (arr2[i] > arr2[i - 1] && arr1[i] > arr1[i - 1]) {
            current.true = Math.min(
                current.true,
                map.true + 1,
            );
            current.false = Math.min(
                current.false,
                map.false,
            );
        }
        map = current;
    }
    return Math.min(map.false, map.true);
};

console.log(findSwaps(arr1, arr2));

実行結果

1

計算量について

このアルゴリズムは配列を一度走査するだけで済むため、時間計算量は O(n) です。また、各ステップで保持する必要があるのは直前の位置の2つの状態だけなので、空間計算量は O(1) となります。全てのスワップの組み合わせを総当たりで試す必要がないため、入力サイズが大きくなっても高速かつ安定して動作する点が大きなメリットです。