Skip to content

1257. Smallest Common Region 👍

  • Time: $O(|\texttt{regions}|)$
  • Space: $O(|\texttt{regions}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  string findSmallestRegion(vector<vector<string>>& regions, string region1,
                            string region2) {
    unordered_map<string, string> parent;
    unordered_set<string> ancestors;  // region1's ancestors

    for (const vector<string>& region : regions)
      for (int i = 1; i < region.size(); ++i)
        parent[region[i]] = region[0];

    // Add all the region1's ancestors.
    while (region1 != "") {
      ancestors.insert(region1);
      region1 = parent[region1];  // Region1 becomes "" in the end
    }

    // Go up from region2 until meet any of region1's ancestors.
    while (!ancestors.count(region2))
      region2 = parent[region2];

    return region2;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
    Map<String, String> parent = new HashMap<>();
    Set<String> ancestors = new HashSet<>(); // region1's ancestors

    for (List<String> region : regions)
      for (int i = 1; i < region.size(); ++i)
        parent.put(region.get(i), region.get(0));

    // Add all the region1's ancestors.
    while (region1 != null) {
      ancestors.add(region1);
      region1 = parent.get(region1); // Region1 becomes null in the end.
    }

    // Go up from region2 until meet any of region1's ancestors.
    while (!ancestors.contains(region2))
      region2 = parent.get(region2);

    return region2;
  }
}