Pythonでソート済み3つの配列から選ぶ三つ組の（max − min）を最小化するアルゴリズム

問題概要

サイズが異なっていても構わない、3つのソート済み配列 A、B、C が与えられているとします。このとき、それぞれの配列から1要素ずつ選んだ三つ組 (A[i], B[j], C[k]) について、「三つ組の中の最大値 − 最小値」の絶対差を求め、その最小値を計算するのが目的です。

例として、入力が次のような場合を考えてみましょう。

• A : [2, 5, 6, 9, 11]
• B : [7, 10, 16]
• C : [3, 4, 7, 7]

このとき出力は 1 になります。A[i] = 6、B[j] = 7、C[k] = 7 を選べば、max(A[i], B[j], C[k]) − min(A[i], B[j], C[k]) = |7 − 6| = 1 となり、これが最小の差だからです。

解法のアプローチ

3つの配列はすべてソート済みであることを利用すると、各配列の末尾からポインタを動かしていく効率的な方法が使えます。考え方はシンプルで、「現在三つ組の中で最も大きい値を持つ要素のポインタだけを1つ減らす」ことを繰り返すことで、差を縮める可能性のある組み合わせを探索していきます。

手順は以下の通りです。

1. i := A のサイズ − 1、j := B のサイズ − 1、k := C のサイズ − 1 と初期化する。
2. minimum_difference := |max(A[i], B[j], C[k]) − min(A[i], B[j], C[k])| で初期化する。
3. i、j、k のいずれも -1 でない間、以下を繰り返す。
   • current_diff := 現在の三つ組の最大値と最小値の絶対差を計算する。
   • current_diff が minimum_difference より小さければ、minimum_difference を更新する。
   • maximum_term := 三つ組の中の最大値とする。
   • A[i] が maximum_term と等しければ i を減らし、そうでなければ B[j] が等しければ j を減らし、それ以外なら k を減らす。
4. ループ終了後、minimum_difference を返す。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

def solve(A, B, C):
    i = len(A) - 1
    j = len(B) - 1
    k = len(C) - 1
    minimum_difference = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]))
    while i != -1 and j != -1 and k != -1:
        current_diff = abs(max(A[i], B[j], C[k]) - min(A[i], B[j], C[k]))
        if current_diff < minimum_difference:
            minimum_difference = current_diff
        maximum_term = max(A[i], B[j], C[k])
        if A[i] == maximum_term:
            i -= 1
        elif B[j] == maximum_term:
            j -= 1
        else:
            k -= 1
    return minimum_difference

A = [2, 5, 6, 9, 11]
B = [7, 10, 16]
C = [3, 4, 7, 7]
print(solve(A, B, C))

入力

A = [2, 5, 6, 9, 11]
B = [7, 10, 16]
C = [3, 4, 7, 7]

出力

1

計算量について

各ループの反復では必ずいずれかのポインタが1つ減るため、時間計算量は O(len(A) + len(B) + len(C)) となり、非常に効率的です。追加のメモリも定数しか使わないため、空間計算量は O(1) です。全組み合わせを総当たりする O(n³) の方法と比べると、大きな入力に対しても実用的に動作します。