Smallest Common Region

Problem Statement

In this task, you are provided with a hierarchical structure of geographic regions represented as lists, where each list embodies a hierarchy of containment. The first region in each list is considered to encompass all other regions listed after it. It’s similar to parent-child relationships where the parent includes the children, and adjacent siblings don't overlap in coverage.

The challenge is to find the smallest or most immediate common region that encompasses two given regions, referred to here as region1 and region2. Each region within the nested lists implicitly or explicitly contains itself. For example, given specific region relationships modeled in the lists, and two regions for inquiry, you should determine the most immediate 'parent' region that is an ancestor to both. There should not be any scenario within the input data where one region is contained by multiple other regions at the same hierarchical level.

The problem also comes with a set of assurances:

• The structure is well-formed such that each child has only one direct parent.
• The smallest region that can contain both region1 and region2 is guaranteed to exist.

Examples

Example 1

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

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.

Approach and Intuition

The problem essentially boils down to finding the lowest common ancestor in a tree that is not explicitly defined but inferred from lists. Here's a step-by-step strategy to approach this:

1. Build Parent Map:

   • Create a dictionary parent_map where each child region points to its immediate parent.
   • Iterate through each list in regions, assigning the first element as the parent of all subsequent ones.

2. Trace Ancestors of region1:

   • Starting from region1, move up the hierarchy using the parent_map.
   • Store each ancestor in a set ancestors1.

3. Find First Common Ancestor:

   • Starting from region2, trace its path to the root.
   • The first region found that also exists in ancestors1 is the lowest common region.

4. Guarantees Ensure Validity:

   • The problem guarantees a valid containment tree with one root and no cycles, so this approach will always yield a result.

This strategy ensures optimal performance and correctness, utilizing the tree's unique properties and a simple traversal mechanism to identify the common ancestor.

Solutions

class Solution {
    vector<string> getPathFromRoot(
        string currentNode, unordered_map<string, string>& parentMapping) {
        vector<string> pathList;
        pathList.push_back(currentNode);
    
        while (parentMapping.find(currentNode) != parentMapping.end()) {
            string parent = parentMapping[currentNode];
            pathList.push_back(parent);
            currentNode = parent;
        }
        reverse(pathList.begin(), pathList.end());
        return pathList;
    }
    
public:
    string locateSmallestCommonRegion(vector<vector<string>>& areas, string area1,
                                       string area2) {
        unordered_map<string, string> regionHierarchy;
        for (auto& region : areas) {
            string parent = region[0];
            for (int idx = 1; idx < region.size(); ++idx) {
                regionHierarchy[region[idx]] = parent;
            }
        }
    
        auto pathForArea1 = getPathFromRoot(area1, regionHierarchy);
        auto pathForArea2 = getPathFromRoot(area2, regionHierarchy);
    
        int i = 0, j = 0;
        string commonAncestor;
        while (i < pathForArea1.size() && j < pathForArea2.size() && pathForArea1[i] == pathForArea2[j]) {
            commonAncestor = pathForArea1[i];
            i++;
            j++;
        }
    
        return commonAncestor;
    }
};