Smallest Common Region

medium tree lowest common ancestor hash map

Problem

You are given a list of regions where each entry lists a parent region followed by its direct sub-regions. Region X contains region Y if X is the same as Y or X transitively contains Y. Given two regions region1 and region2, return the smallest region that contains both of them.

Inputregions = [[Earth,NA,SA],[NA,US,Canada],[US,NY,SF]], region1 = SF, region2 = Canada

OutputNA

SF sits under US under NA; Canada sits directly under NA. Their lowest common ancestor is NA.

region1

region2

def find_smallest_region(regions, region1, region2):
    parent = {}
    for group in regions:
        for child in group[1:]:
            parent[child] = group[0]
    ancestors = set()
    node = region1
    while node:
        ancestors.add(node)
        node = parent.get(node)
    node = region2
    while node not in ancestors:
        node = parent.get(node)
    return node

function findSmallestRegion(regions, region1, region2) {
  const parent = new Map();
  for (const group of regions)
    for (let i = 1; i < group.length; i++) parent.set(group[i], group[0]);
  const ancestors = new Set();
  for (let node = region1; node; node = parent.get(node)) ancestors.add(node);
  let node = region2;
  while (!ancestors.has(node)) node = parent.get(node);
  return node;
}

class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parent = new HashMap<>();
        for (List<String> group : regions)
            for (int i = 1; i < group.size(); i++) parent.put(group.get(i), group.get(0));
        Set<String> ancestors = new HashSet<>();
        for (String node = region1; node != null; node = parent.get(node)) ancestors.add(node);
        String node = region2;
        while (!ancestors.contains(node)) node = parent.get(node);
        return node;
    }
}

string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
    unordered_map<string, string> parent;
    for (auto& group : regions)
        for (int i = 1; i < (int)group.size(); i++) parent[group[i]] = group[0];
    unordered_set<string> ancestors;
    for (string node = region1; !node.empty(); node = parent.count(node) ? parent[node] : "")
        ancestors.insert(node);
    string node = region2;
    while (!ancestors.count(node)) node = parent[node];
    return node;
}

Explanation

"Smallest region containing both" is really the lowest common ancestor of two nodes in a hierarchy. Since each region knows only its sub-regions, we first flip that into a child → parent map so we can climb upward.

We build the parent map by scanning each group: the first entry is the parent and every later entry is a child pointing back to it.

Then we walk up from region1, dropping every region we pass into an ancestors set — this is the full chain from region1 up to the root. Next we walk up from region2, and the first region that already appears in that set is the lowest shared ancestor, which we return.

Example: region1 = SF, region2 = Canada. Climbing from SF gives the set {SF, US, NA, Earth}. Climbing from Canada we check Canada (not in the set), then move to its parent NA, which is in the set — so the answer is NA.

The set lets us check membership instantly, so the cost is one pass to build the map plus two short climbs up the hierarchy.

Time: O(N + h) Space: O(N)