Pythonでサブ配列を1回反転するだけで配列がソートされるかどうかを判定する方法

すべての要素がユニーク（重複なし）である配列 nums があるとします。この配列の部分配列（サブ配列）を1つだけ反転したとき、配列全体がソートされた状態になるかどうかを判定するのが本記事のテーマです。なお、配列がすでにソート済みの場合も True を返します。

たとえば、入力が nums = [4,6,27,25,15,9,37,42] の場合を考えてみましょう。[27,25,15,9] の部分を反転すると [4,6,9,15,25,27,37,42] となり、配列全体が昇順に整列します。したがって、この場合の出力は True になります。

アルゴリズムのアプローチ

この問題は、配列を一度走査するだけで線形時間 O(n) で判定できます。手順は以下の通りです。

• n を配列 nums のサイズとします。
• 要素が1つしかない場合は、すでにソートされているとみなし True を返します。
• i := 1 として、昇順が続いている限りインデックスを進めます。
• nums[i-1] < nums[i] が成り立つ間は昇順なので i を進め、初めて崩れた位置でループを抜けます。
• j := i から始め、j < n かつ nums[j] < nums[j-1] の間（＝降順になっている区間）、j を進めて反転候補の範囲を特定します。
• 反転候補の先頭要素が、直前の昇順区間の末尾より小さい場合は、反転しても整合しないため False を返します。
• j == n に達していれば、末尾まで反転で収まるため True を返します。
• 残りの区間についても k := j 以降が昇順に保たれているかを確認し、崩れていれば False、最後まで問題なければ True を返します。

実装例（Pythonコード）

def solve(nums):
    n = len(nums)
    if n == 1:
        return True

    i = 1
    for i in range(1, n):
        if nums[i - 1] < nums[i]:
            if i == n:
                return True
        else:
            break

    j = i
    while j < n and nums[j] < nums[j - 1]:
        if i > 1 and nums[j] < nums[i - 2]:
            return False
        j += 1

    if j == n:
        return True

    k = j
    if nums[k] < nums[i - 1]:
        return False

    while k > 1 and k < n:
        if nums[k] < nums[k - 1]:
            return False
        k += 1
    return True

nums = [4,6,27,25,15,9,37,42]
print(solve(nums))

入力

[4,6,27,25,15,9,37,42]

出力

True

計算量の評価

このアルゴリズムは配列を高々数回走査するだけで完了するため、時間計算量は O(n) です。また、追加のデータ構造を使用しないため、空間計算量は O(1) となります。配列全体を実際に反転・コピーして比較する方法（O(n) の追加メモリが必要）よりも効率的で、大きな入力にも対応できます。

まとめ

「1つのサブ配列を反転するだけでソートできるか」という問題は、昇順→降順→昇順というパターンを線形走査で検出することで解決できます。境界条件（すでにソート済み、要素数1、反転区間が配列の端に接しているケースなど）を丁寧に扱うことが、正確な実装のポイントです。