Code Implementation

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

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

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

var findSmallestRegion = function(regions, region1, region2) {
    const parent = {};
    for (const region of regions) {
        for (let i = 1; i < region.length; i++) {
            parent[region[i]] = region[0];
        }
    }
    const ancestors = new Set();
    while (region1) {
        ancestors.add(region1);
        region1 = parent[region1];
    }
    while (region2) {
        if (ancestors.has(region2)) return region2;
        region2 = parent[region2];
    }
    return "";
};

Problem Description

You are given a list of regions, where each region is represented as a list of strings. The first element of each list is the parent region, followed by its direct subregions. Given two region names, region1 and region2, your task is to find their smallest common region — the lowest region in the hierarchy that contains both region1 and region2.

Key constraints:

• There is exactly one valid answer for each query.
• Regions form a tree (no cycles, one parent per region except the root).
• Do not reuse elements; each region appears only once as a subregion.

Example 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"

Thought Process

At first glance, this problem resembles finding the lowest common ancestor (LCA) in a tree structure. Each region can be seen as a node, with parent-child relationships defined by the input. To find the smallest common region for two given regions, we need to trace their paths up to the root and find where those paths intersect.

A brute-force approach might involve building the entire tree, then for each query, traversing from both regions up to the root and comparing their paths. However, this can be simplified by using a hash map to store parent relationships, making ancestor lookups efficient. The key insight is that we do not need to build the entire tree structure; we only need to know each region's immediate parent.

By storing the path from one region to the root in a set, we can then walk up from the other region and return the first ancestor found in the set — this is their lowest common ancestor.

Solution Approach

• Step 1: Build Parent Map
  • Iterate over the regions list.
  • For each region list, map every subregion to its parent using a hash map or dictionary.
• Step 2: Trace Ancestors of First Region
  • Starting from region1, walk up the parent map, adding each region to a set.
  • Continue until you reach the root (a region with no parent).
• Step 3: Find First Common Ancestor
  • Starting from region2, walk up the parent map.
  • The first time you encounter a region that is in the set of region1's ancestors, return it — this is the smallest common region.
• Justification:
  • Using a hash map for parent lookups ensures O(1) access.
  • Using a set for ancestors allows O(1) existence checks.
  • This approach is efficient and leverages the tree structure of the data.

Example Walkthrough

Let's use the sample 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"

1. Build Parent Map:
   • North America → Earth
   • South America → Earth
   • United States → North America
   • Canada → North America
   • New York → United States
   • Boston → United States
   • Ontario → Canada
   • Quebec → Canada
   • Brazil → South America
2. Trace Ancestors of "Quebec":
   • Quebec → Canada
   • Canada → North America
   • North America → Earth
   • Earth → (no parent)
   • Ancestors set = {"Quebec", "Canada", "North America", "Earth"}
3. Walk Up from "New York":
   • New York: not in ancestors
   • Parent: United States (not in ancestors)
   • Parent: North America (is in ancestors!)
   • Return "North America"

Thus, the smallest common region is "North America".

Time and Space Complexity

• Brute-force Approach:
  • Building full paths for both regions and comparing them could take O(N^2) time if done naively, where N is the number of regions.
• Optimized Approach:
  • Parent map construction: O(N), where N is the total number of regions and subregions.
  • Tracing ancestors: O(H), where H is the height of the tree (at most N in the worst case).
  • Space: O(N) for the parent map and O(H) for the ancestor set.
  • Overall: O(N) time and O(N) space.

This efficiency is possible because each lookup and ancestor check is O(1) due to hash maps and sets.

Summary

The solution to the Smallest Common Region problem leverages the tree structure of the input data. By mapping each region to its parent, we can efficiently trace the ancestry of any region. The intersection of ancestor paths yields the smallest region containing both target regions. This approach is both simple and efficient, using hash maps and sets for quick lookups, and elegantly reduces a potentially complex tree traversal problem to a series of parent lookups and set operations.