Задача: 1257. Smallest Common Region
Сложность: medium

Вам даны списки регионов, в которых первый регион каждого списка включает все остальные регионы этого списка. Естественно, если регион x содержит другой регион y, то x больше y. Также, по определению, регион x содержит сам себя. Даны два региона: region1 и region2, верните наименьший регион, который содержит их оба. Если вам даны регионы r1, r2 и r3 такие, что r1 включает r3, то гарантированно не существует r2 такого, что r2 включает r3. Гарантированно существует наименьший регион.

Пример:

Input:
regions = [["Earth","North America","South America"],
["North America","United States","Canada"],
["United States","New York","Boston"],
["Canada","Ontario","Quebec"],
["South America","Brazil"]],
region1 = "Quebec",
region2 = "New York"
Output: "North America"

👨‍💻 Алгоритм:

1⃣Построим дерево регионов, где каждый регион указывает на своего родителя.

2⃣Используя родительскую информацию, найдем путь от каждого региона до корня.

3⃣Найдем последний общий регион в путях двух заданных регионов.

😎 Решение:

var findSmallestRegion = function(regions, region1, region2) {
    const parent = new Map();

    regions.forEach(regionList => {
        for (let i = 1; i < regionList.length; i++) {
            parent.set(regionList[i], regionList[0]);
        }
    });

    const ancestors1 = new Set();
    while (region1) {
        ancestors1.add(region1);
        region1 = parent.get(region1);
    }

    while (!ancestors1.has(region2)) {
        region2 = parent.get(region2);
    }

    return region2;
};

Ставь 👍 и забирай 📚 Базу знаний