Условие

Дан массив arr. Нужно найти все пары с минимальной абсолютной разницей и вернуть их в порядке возрастания.

Примеры

Input: [4, 2, 1, 3] Output: [[1, 2], [2, 3], [3, 4]] Explanation: Минимальная абсолютная разница равна 1. Перечислите все пары с разницей, равной 1, в порядке возрастания.

Input: [1, 3, 6, 10, 15] Output: [[1, 3]]

Input: [3, 8, -10, 23, 19, -4, -14, 27] Output: [[-14, -10], [19, 23], [23, 27]]

Решение

fun minimumAbsDifference(arr: IntArray): List<List<Int>> {
    // Находим минимальный и максимальный элементы массива
    var minValue = Int.MAX_VALUE
    var maxValue = Int.MIN_VALUE
    for (num in arr) {
        if (num < minValue) minValue = num
        if (num > maxValue) maxValue = num
    }

    // Создаем булевый массив для хранения присутствующих чисел
    val exists = BooleanArray(maxValue - minValue + 1)
    for (num in arr) {
        exists[num - minValue] = true
    }

    var minDiff = Int.MAX_VALUE
    val result = mutableListOf<List<Int>>()
    var prev = -1

    // Проходим по булевому массиву, находя минимальную разницу
    for (i in exists.indices) {
        if (exists[i]) {
            if (prev != -1) {
                val diff = i - prev
                if (diff < minDiff) {
                    minDiff = diff
                    result.clear()
                }
                if (diff == minDiff) {
                    result.add(listOf(prev + minValue, i + minValue))
                }
            }
            prev = i
        }
    }
    return result
}

Временная сложность

O(n + m), где n — длина массива, m — диапазон значений в arr.

Пространственная сложность

O(m), так как используется булевый массив размера maxValue - minValue + 1.