Problem

You are given some lists of regions where the first region of each list directly contains all other regions in that list.

If a region x contains a region y directly , and region y contains region z directly , then region x is said to contain region z indirectly. Note that region x also indirectly contains all regions indirectly containd in y.

Naturally, if a region x contains (either directly or indirectly) another region y, then x is bigger than or equal to y in size. Also, by definition, a region x contains itself.

Given two regions: region1 and region2, return the smallest region that contains both of them.

It is guaranteed the smallest region exists.

Examples

Example 1:

1
2
3
4
5
6
7
8

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"

Example 2:

1
2

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

Constraints:

  • 2 <= regions.length <= 10^4
  • 2 <= regions[i].length <= 20
  • 1 <= regions[i][j].length, region1.length, region2.length <= 20
  • region1 != region2
  • regions[i][j], region1, and region2 consist of English letters.
  • The input is generated such that there exists a region which contains all the other regions, either directly or indirectly.
  • A region cannot be directly contained in more than one region.

Solution

Method 1 – Parent Mapping and Ancestor Path

Intuition

Build a parent map for each region. For both region1 and region2, trace their ancestors up to the root. The first common ancestor is the answer (lowest common ancestor in a tree).

Approach

  1. Build a map from each region to its parent.
  2. For region1, collect all ancestors up to the root in a set.
  3. For region2, walk up to the root and return the first region found in region1’s ancestor set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        unordered_map<string, string> parent;
        for (auto& reg : regions) {
            for (int i = 1; i < reg.size(); ++i)
                parent[reg[i]] = reg[0];
        }
        unordered_set<string> path;
        while (region1 != "") {
            path.insert(region1);
            region1 = parent.count(region1) ? parent[region1] : "";
        }
        while (region2 != "") {
            if (path.count(region2)) return region2;
            region2 = parent.count(region2) ? parent[region2] : "";
        }
        return "";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;
class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parent = new HashMap<>();
        for (List<String> reg : regions) {
            for (int i = 1; i < reg.size(); ++i)
                parent.put(reg.get(i), reg.get(0));
        }
        Set<String> path = new HashSet<>();
        while (region1 != null) {
            path.add(region1);
            region1 = parent.get(region1);
        }
        while (region2 != null) {
            if (path.contains(region2)) return region2;
            region2 = parent.get(region2);
        }
        return "";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def findSmallestRegion(self, regions, region1, region2):
        parent = {}
        for reg in regions:
            for r in reg[1:]:
                parent[r] = reg[0]
        path = set()
        while region1:
            path.add(region1)
            region1 = parent.get(region1)
        while region2:
            if region2 in path:
                return region2
            region2 = parent.get(region2)
        return ""

Complexity

  • ⏰ Time complexity: O(N) — N = total number of regions.
  • 🧺 Space complexity: O(N) — For parent map and ancestor set.