Условие

Даны два списка строк list1 и list2, представляющие любимые рестораны двух человек. Найдите все рестораны с минимальной суммой индексов, где строки присутствуют в обоих списках.

Примеры

Input: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"], list2 = ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] Output: ["Shogun"] Explanation: "Shogun" присутствует в обоих списках с суммой индексов 0 (в list1) + 3 (в list2) = 3.

Input: list1 = ["Shogun", "Tapioca Express", "Burger King", "KFC"], list2 = ["KFC", "Shogun", "Burger King"] Output: ["Shogun"] Explanation: "Shogun" имеет минимальную сумму индексов 1 (в list1) + 1 (в list2) = 2.

Input: list1 = ["happy", "sad", "good"], list2 = ["sad", "happy", "good"] Output: ["sad", "happy"] Explanation: У "sad" и "happy" одинаковая минимальная сумма индексов.

Решение

fun findRestaurant(list1: Array<String>, list2: Array<String>): Array<String> {
    val indexMap = mutableMapOf<String, Int>() // Мапа для хранения индексов элементов из list1
    val result = mutableListOf<String>()
    var minSum = Int.MAX_VALUE // Минимальная сумма индексов

    // Сохраняем индексы всех элементов из list1
    for (i in list1.indices) {
        indexMap[list1[i]] = i
    }

    // Проверяем элементы из list2
    for (j in list2.indices) {
        val restaurant = list2[j]
        if (restaurant in indexMap) {
            val sum = j + indexMap[restaurant]!! // Сумма индексов
            when {
                sum < minSum -> { // Найдена новая минимальная сумма
                    minSum = sum
                    result.clear()
                    result.add(restaurant)
                }
                sum == minSum -> { // Сумма равна минимальной, добавляем ресторан
                    result.add(restaurant)
                }
            }
        }
    }

    return result.toTypedArray() // Возвращаем результат в виде массива
}

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

O(n + m), где n и m — размеры списков.

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

O(n), для хранения индексов первого списка.