1. Идея

Нужно найти минимальное значение |a_i - a_j| среди всех пар разных элементов.

Перебирать все пары нельзя: их n * (n - 1) / 2, а при n до 2 * 10^5 это слишком много.

Ключевая идея: если отсортировать массив, то минимальная разница обязательно найдётся среди соседних элементов в отсортированном порядке.

После сортировки достаточно пройти по массиву и найти минимум среди значений a[i] - a[i - 1].

2. Наблюдения

Наблюдение 1

После сортировки массив становится неубывающим:

a[0] <= a[1] <= a[2] <= ... <= a[n-1]

Тогда для соседних элементов разность уже неотрицательна, и модуль не нужен:

|a[i] - a[i - 1]| = a[i] - a[i - 1]

Наблюдение 2

Почему минимальная разница ищется именно среди соседей после сортировки?

Пусть есть два элемента a[i] и a[j], где i < j. Тогда между ними в отсортированном массиве могут стоять другие элементы.

Разность между крайними элементами равна:

a[j] - a[i]

Но если между ними есть хотя бы один элемент, то хотя бы одна из соседних разностей на этом отрезке будет не больше этой общей разности. Значит, искать ответ среди далёких пар не нужно: достаточно проверить соседние.

Наблюдение 3

Если в массиве есть одинаковые числа, то ответ сразу может быть 0, потому что для них модуль разности равен нулю. После сортировки одинаковые элементы окажутся рядом, и алгоритм это автоматически найдёт.

3. Алгоритм

1. Считать n.
2. Считать массив из n чисел.
3. Отсортировать массив.
4. Взять начальный ответ как разность первых двух элементов: a[1] - a[0].
5. Пройти по массиву с индекса 2 до n - 1:
   • вычислить diff = a[i] - a[i - 1];
   • если diff < ans, обновить ответ.
6. Вывести ans.

4. Почему это работает

Докажем, что алгоритм действительно находит минимальную возможную разницу.

После сортировки рассмотрим любую пару элементов a[i] и a[j], где i < j.

Их разность равна a[j] - a[i]. Она раскладывается в сумму соседних разностей:

a[j] - a[i] = (a[i+1] - a[i]) + (a[i+2] - a[i+1]) + ... + (a[j] - a[j-1])

Все слагаемые неотрицательны, потому что массив отсортирован.

Если бы каждая соседняя разность на этом участке была строго больше, чем a[j] - a[i], это невозможно, потому что их сумма тогда была бы тем более больше. Значит, среди соседних разностей на пути от i до j найдётся хотя бы одна, не превосходящая a[j] - a[i].

Следовательно, для любой пары элементов существует соседняя пара с разностью не больше. Значит, минимальная разность среди всех пар обязательно достигается на соседних элементах отсортированного массива.

Именно их и проверяет алгоритм, значит он находит правильный ответ.

5. Сложность

• Сортировка: O(n log n)
• Один проход по массиву: O(n)

Итоговая сложность: O(n log n)

Дополнительная память:

• сортировка массива чисел: O(n) на хранение массива

6. Код на C++17

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    long long ans = a[1] - a[0];
    for (int i = 2; i < n; i++) {
        long long diff = a[i] - a[i - 1];
        if (diff < ans) {
            ans = diff;
        }
    }

    cout << ans << "\n";
    return 0;
}

7. Код на Python 3

n = int(input())
a = list(map(int, input().split()))

a.sort()

ans = a[1] - a[0]
for i in range(2, n):
    diff = a[i] - a[i - 1]
    if diff < ans:
        ans = diff

print(ans)