1436. Destination City

Задача

Дан массив путей [cityA, cityB]. Верните город назначения — город без исходящих путей.

Примеры

Пример 1

Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
Output: "Sao Paulo"

Пояснение

Маршрут: “London” → “New York” → “Lima” → “Sao Paulo”. Город назначения — “Sao Paulo”.

Пример 2

Input: paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"

Пояснение

Маршрут: “D” → “B” → “C” → “A”. Город назначения — “A”.

Пример 3

Input: paths = [["A","Z"]]
Output: "Z"

Решение

Решение

// Time Complexity:  O(n)
// Space Complexity: O(n)
var destCity = function(paths) {
    const outgoing = new Set();
 
    for (const [source, target] of paths) {
        outgoing.add(source);
    }
 
    for (const [source, target] of paths) {
        if (!outgoing.has(target)) return target;
    }
};