Pythonで配列を互いに素な左右の部分配列に分割する方法を解説

問題の概要

配列 nums が与えられたとき、これを「left」と「right」という2つの部分配列に分割します。この分割は、以下の条件を満たす必要があります。

• left 内のすべての要素が、right 内のどの要素以下であること
• left と right がどちらも空でないこと
• left のサイズが可能な限り小さいこと

そして、このような分割を行った後の left の長さを求めます。

具体例

たとえば、入力が nums = [5,0,3,8,6] の場合、出力は 3 になります。これは、left 配列が [5,0,3]、right 部分配列が [8,6] に分割されるためです。

解法のアプローチ

この問題は、配列を一度だけ走査しながら最大値を追跡することで、O(n) の計算量で効率的に解けます。以下の変数を使用します。

• mx: 現在の left 部分配列の最大値（初期値は null）
• nmx: 直近までに現れた要素の最大値（将来の候補）
• temp: 分割境界のインデックス
• temp2: 現在走査中の位置を表すカウンター

各要素に対して、以下のように処理を進めます。

• mx が未設定（null）の場合：最初の要素なので、mx と nmx をその要素で初期化し、temp を現在位置に設定します。
• i >= mx の場合：この要素は left に入れても条件を壊さないため、そのまま進みます。必要に応じて nmx を更新します。
• i < mx の場合：left の最大値より小さい要素が出現したため、分割点をここまで延ばす必要があります。temp を現在位置に更新し、mx を nmx（直近までの最大値）に置き換えます。

最後に temp + 1 を返すことで、left の長さが求まります。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def solve(nums):
    mx = None
    temp = None
    nmx = None
    temp2 = 0

    for i in nums:
        if mx is None:
            mx = i
            nmx = i
            temp = temp2
            temp2 += 1
            continue

        if i >= mx:
            temp2 += 1
            if i > nmx:
                nmx = i
            continue
        else:
            temp = temp2
            temp2 += 1
            mx = nmx
            continue

    return temp + 1

nums = [5,0,3,8,6]
print(solve(nums))

入力

[5,0,3,8,6]

出力

3

計算量について

このアルゴリズムの計算量は以下の通りです。

• 時間計算量： O(n) — 配列を一度だけ走査すればよいため、非常に高速です。
• 空間計算量： O(1) — 追加のデータ構造が不要で、メモリ使用量は一定です。

最大値の追跡というシンプルな発想で、配列の分割問題を線形時間で解決できる点が、この手法の大きな魅力です。