Pythonで隣接する要素のインデックス差の最小値を求めるプログラム

問題の概要

数値のリスト nums が与えられたとき、nums[i] ≤ nums[j] を満たす2つの数値について、nums 内に (nums[i], nums[j]) の間に該当する数が存在しない場合、この2つの数値は「隣接している」とみなします。ここでの課題は、nums[j] と nums[i] が隣接関係にあるとき、そのインデックス差 |j − i| の最小値を求めることです。

たとえば、入力が nums = [1, -9, 6, -6, 2] の場合、出力は 2 になります。これは、値 2 と 6 が隣接しており、それぞれのインデックスが 2 つ離れているためです。

解決のためのアプローチ

この問題は、次の3つのステップで解くことができます。

1. インデックスマップの作成： 各値が出現するインデックスをすべて辞書に記録します。
2. 同一値同士の距離を確認： 同じ値を持つインデックス列の中で、連続するインデックスの差の最小値を求めます。
3. 隣接する値同士の距離を確認： 値をソートしたうえで、隣り合う値のインデックスリスト同士を二ポインタ法で比較し、最小のインデックス差を更新していきます。

ポイントは、値をソートした後に「隣り合う値」だけを比較すればよいという点です。隣接と定義される2つの数の間には別の値が存在しないため、それらは必ずソート後のユニークな値の並びで連続した位置に現れます。

アルゴリズムの詳細な手順

• indexes := 新しいマップ（辞書）を作成する
• リスト A の各インデックス i と値 x について、indexes[x] の末尾に i を追加する
• ans := A のサイズで初期化する
• indexes のすべての値（インデックスリスト）row について、i を 0 から row のサイズ − 2 まで繰り返し、ans := min(ans, row[i + 1] − row[i]) を更新する
• vals := indexes のキーをソートしたリストを作成する
• k を 0 から vals のサイズ − 2 まで繰り返す：
  • r1 := indexes[vals[k]]、r2 := indexes[vals[k + 1]] を取得する
  • i = j = 0 として初期化する
  • i < len(r1) かつ j < len(r2) の間、次を繰り返す：
    • ans := min(ans, |r1[i] − r2[j]|) を更新する
    • r1[i] < r2[j] なら i を 1 増やし、そうでなければ j を 1 増やす
• 最終的な ans を返す

Pythonでの実装例

理解を深めるために、以下の実装をご覧ください。

from collections import defaultdict
class Solution:
    def solve(self, A):
        indexes = defaultdict(list)
        for i, x in enumerate(A):
            indexes[x].append(i)
        ans = len(A)
        for row in indexes.values():
            for i in range(len(row) - 1):
                ans = min(ans, row[i + 1] - row[i])
        vals = sorted(indexes)
        for k in range(len(vals) - 1):
            r1 = indexes[vals[k]]
            r2 = indexes[vals[k + 1]]
            i = j = 0
            while i < len(r1) and j < len(r2):
                ans = min(ans, abs(r1[i] - r2[j]))
                if r1[i] < r2[j]:
                    i += 1
                else:
                    j += 1
        return ans
ob = Solution()
nums = [1, -9, 6, -6, 2]
print(ob.solve(nums))

入力

[1, -9, 6, -6, 2]

出力

2

計算量について

このアルゴリズムの時間計算量は O(n log n) です。ユニークな値のソートに O(n log n) かかり、各値ペアの二ポインタ比較は全体で O(n) 程度に収まるためです。空間計算量は O(n) となり、すべてのインデックスを格納するための辞書が必要になります。全ペアを総当たりする O(n²) の素朴な解法と比べ、大規模な入力でも高速に動作するのが特徴です。