Pythonで2つの配列における有効なペアの最大距離を求めるプログラム

非増加（降順）に並べられた2つの配列 nums1 と nums2 が与えられているとします。インデックスのペア (i, j) は、0 <= i < len(nums1)、0 <= j < len(nums2) を満たし、かつ i <= j と nums1[i] <= nums2[j] の両方が成り立つときに「有効なペア」とみなされます。ペアの距離は (j - i) で表され、この問題の目的は、すべての有効なペアの中から最大の距離を見つけることです。有効なペアがひとつも存在しない場合は 0 を返します。

たとえば、nums1 = [60,40,15,10,5]、nums2 = [115,30,25,15,10] という入力が与えられた場合、出力は 1 になります。このとき有効なペアは (0,0)、(2,2)、(2,3)、(3,3)、(3,4)、(4,4) であり、最大距離はペア (2,3) または (3,4) における 1 になるためです。

解き方のアルゴリズム

この問題は、次の手順に従って解くことができます。

• nums1 の最後の要素が nums2 の最初の要素より大きい場合は、有効なペアが存在しないため 0 を返します。
• i := 0、j := 0、max_dist := 0 として初期化します。
• i が nums1 のサイズより小さい間、次の処理を繰り返します。
  • j が nums2 のサイズより小さく、かつ nums1[i] <= nums2[j] が成り立つ場合は、max_dist を max_dist と (j - i) のうち大きい方の値で更新し、j を 1 増やします。
  • それ以外の場合は、j と i をそれぞれ 1 増やします。
• 最後に max_dist を返します。

アルゴリズムのポイント

この解法では「二ポインタ（two-pointer）」と呼ばれるテクニックを使用しています。両方の配列が降順にソートされているという性質を利用することで、考えられるすべてのペアを総当たりする O(n × m) のアプローチよりも効率的な、O(n + m) の計算量で答えを求めることができます。

実装例

理解を深めるために、以下のPythonでの実装例を見てみましょう。

def solve(nums1, nums2):
   if nums1[len(nums1)-1] > nums2[0]:
      return 0

   i = j = max_dist = 0
   while i < len(nums1):
      if j < len(nums2) and nums1[i] <= nums2[j]:
         max_dist = max(max_dist, j-i)
         j += 1
      else:
         j += 1
         i += 1

   return max_dist

nums1 = [60,40,15,10,5]
nums2 = [115,30,25,15,10]
print(solve(nums1, nums2))

入力

[60,40,15,10,5], [115,30,25,15,10]

出力

1