Problem Description

You are given multiple lists of regions where each list follows a hierarchical structure - the first region in each list directly contains all other regions in that list.

The containment relationship works as follows:

• If region x directly contains region y, and region y directly contains region z, then region x indirectly contains region z
• A region that contains another region (directly or indirectly) is considered bigger than or equal to the contained region
• By definition, every region contains itself

Given two specific regions: region1 and region2, you need to find the smallest region that contains both of them.

For example, if you have lists like [["Earth", "North America", "South America"], ["North America", "United States", "Canada"], ["United States", "New York", "Boston"]], this creates a hierarchy where Earth contains North America, which contains United States, which contains New York and Boston.

The task is to find the lowest common ancestor in this hierarchy - the smallest region that is an ancestor of (or contains) both region1 and region2. The problem guarantees that such a region always exists.

The solution uses a hash table to map each region to its parent region, then traces the path from region1 upward to collect all its ancestors. Finally, it traces from region2 upward until it finds the first common ancestor that was also an ancestor of region1.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves regions with parent-child relationships, forming a hierarchical structure. Each region can be viewed as a node, and the containment relationships form edges between nodes.

Is it a tree?

• Yes: The structure is actually a tree (or forest of trees). Each region has at most one parent (the region that directly contains it), and there are no cycles in the containment relationships. The problem essentially creates a tree where parent nodes contain their child nodes.

DFS

• Yes: We arrive at DFS as the suitable approach for this tree problem.

Conclusion: The flowchart suggests using a DFS approach for finding the smallest common region.

In this problem, we use DFS in two phases:

1. First DFS traversal: Starting from region1, we traverse upward (toward the root) to collect all ancestor regions
2. Second DFS traversal: Starting from region2, we traverse upward until we find the first region that was also an ancestor of region1

This is essentially finding the Lowest Common Ancestor (LCA) in a tree structure, which is a classic application of DFS on trees. The solution builds a parent mapping first, then uses path traversal (a form of DFS) to find the common ancestor.

Intuition

The key insight is recognizing that the region containment relationships form a tree structure. When we have lists like ["Earth", "North America", "South America"], we're essentially being told that "Earth" is the parent of both "North America" and "South America". Each region can only be directly contained by one other region (it has only one parent), making this a tree rather than a general graph.

Once we recognize the tree structure, finding the smallest region that contains both region1 and region2 becomes a classic Lowest Common Ancestor (LCA) problem. Think of it like finding the nearest common boss in a company hierarchy for two employees.

The approach becomes clear when we think about how to find a common ancestor:

1. First, we need to know the chain of command - who contains whom. We build a parent mapping where g[child] = parent for quick lookups.

2. Starting from region1, we can trace our way up the tree by repeatedly looking up parents until we reach the root. We store all these ancestors in a set s - these are all regions that contain region1.

3. Now, starting from region2, we trace upward again. The first region we encounter that's also in set s must be the lowest (smallest) common ancestor - it's the first point where the paths from both regions converge.

This two-pass approach is efficient because we only need to traverse each path once. The first pass marks the path from region1 to root, and the second pass finds where region2's path intersects with it. The intersection point is guaranteed to be the smallest region containing both.

Learn more about Tree, Depth-First Search and Breadth-First Search patterns.

Solution Approach

The implementation follows the intuition directly using a hash table to build the parent relationships and then performing two traversals to find the LCA.

Step 1: Build the Parent Mapping

We iterate through all region lists and create a hash table g where each child region maps to its parent:

g = {}
for r in regions:
    x = r[0]  # parent region (first in list)
    for y in r[1:]:  # all other regions are children
        g[y] = x

For example, if we have ["Earth", "North America", "South America"], we create:

• g["North America"] = "Earth"
• g["South America"] = "Earth"

Step 2: Trace Path from region1 to Root

Starting from region1, we traverse upward by repeatedly looking up parents, storing all ancestors in a set s:

s = set()
x = region1
while x in g:
    s.add(x)
    x = g[x]

This loop continues until we reach a root region (one that has no parent in g). The set s now contains all regions that contain region1.

Step 3: Find First Common Ancestor from region2

Starting from region2, we traverse upward until we find a region that's also in set s:

x = region2
while x in g and x not in s:
    x = g[x]

The loop stops when either:

• We find x in set s (common ancestor found)
• x is not in g (reached a root)

The final value of x is our answer - it's the smallest region that contains both region1 and region2.

Time Complexity: O(n) where n is the total number of regions, as we process each region at most once when building the parent map and during traversals.

Space Complexity: O(n) for storing the parent mapping and the ancestor set.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• Region lists: [["Earth", "Asia", "Africa"], ["Asia", "China", "India"], ["China", "Beijing", "Shanghai"]]
• region1 = "Beijing"
• region2 = "India"
• Task: Find the smallest region containing both Beijing and India

Step 1: Build Parent Mapping

We process each list, where the first element is the parent of all others:

From ["Earth", "Asia", "Africa"]:

• g["Asia"] = "Earth"
• g["Africa"] = "Earth"

From ["Asia", "China", "India"]:

• g["China"] = "Asia"
• g["India"] = "Asia"

From ["China", "Beijing", "Shanghai"]:

• g["Beijing"] = "China"
• g["Shanghai"] = "China"

Our parent map g now looks like:

{
  "Asia": "Earth",
  "Africa": "Earth", 
  "China": "Asia",
  "India": "Asia",
  "Beijing": "China",
  "Shanghai": "China"
}

Step 2: Trace Path from Beijing to Root

Starting from Beijing, we traverse upward collecting ancestors:

• Start: x = "Beijing", s = {}
• "Beijing" is in g, add to s: s = {"Beijing"}, move to parent: x = "China"
• "China" is in g, add to s: s = {"Beijing", "China"}, move to parent: x = "Asia"
• "Asia" is in g, add to s: s = {"Beijing", "China", "Asia"}, move to parent: x = "Earth"
• "Earth" is NOT in g (it's a root), stop

Set s contains all regions that contain Beijing: {"Beijing", "China", "Asia"}

Step 3: Find First Common Ancestor from India

Starting from India, traverse upward until we find a region in set s:

• Start: x = "India"
• "India" is in g and NOT in s, move to parent: x = "Asia"
• "Asia" is in g and IS in s → Found our answer!

Result: "Asia" is the smallest region containing both Beijing and India.

This makes sense because:

• Beijing is contained in: China → Asia → Earth
• India is contained in: Asia → Earth
• Their paths first meet at Asia, making it the lowest common ancestor.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three main parts:

1. Building the parent graph: We iterate through all regions and their sub-regions. If there are m regions with an average of k sub-regions each, this takes O(m * k) time. Since the total number of region relationships is n, this is O(n).
2. Finding ancestors of region1: In the worst case, we traverse from region1 to the root, which could be at most O(n) nodes in a degenerate tree structure.
3. Finding the common ancestor starting from region2: Similarly, this could traverse at most O(n) nodes in the worst case.

Overall, the time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The space usage includes:

1. The parent graph g: This dictionary stores at most n parent-child relationships, requiring O(n) space.
2. The set s: In the worst case, it stores all ancestors of region1, which could be up to O(n) nodes.
3. Variables x, region1, and region2: These use O(1) space.

The total space complexity is O(n) + O(n) + O(1) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling the Case When One Region is the Ancestor of Another

The Problem: The current implementation has a critical bug when one of the input regions is itself an ancestor of the other. For example, if region1 = "United States" and region2 = "New York", where United States directly contains New York, the algorithm will fail to return the correct answer ("United States").

Why It Happens: When collecting ancestors of region1, the code only adds regions found by traversing upward through the parent map. It never adds region1 itself to the ancestors_of_region1 set. Similarly, when traversing from region2, if region2 itself is the common ancestor, it won't be checked against the set before entering the while loop.

Example Failure Case:

regions = [["Earth", "North America"], ["North America", "United States"], ["United States", "New York"]]
region1 = "United States"
region2 = "New York"
# Expected: "United States" (since US contains NY)
# Actual: "North America" (incorrectly goes up one level)

The Solution: Add each region to its own ancestor set before traversing upward:

class Solution:
    def findSmallestRegion(
        self, regions: List[List[str]], region1: str, region2: str
    ) -> str:
        # Build parent-child relationship map
        parent_map = {}
        for region_list in regions:
            parent_region = region_list[0]
            for child_region in region_list[1:]:
                parent_map[child_region] = parent_region
      
        # Collect all ancestors of region1, INCLUDING region1 itself
        ancestors_of_region1 = set()
        current_region = region1
        # Add the starting region first
        ancestors_of_region1.add(current_region)
        # Then traverse up to add all ancestors
        while current_region in parent_map:
            current_region = parent_map[current_region]
            ancestors_of_region1.add(current_region)
      
        # Check if region2 itself is a common ancestor first
        current_region = region2
        if current_region in ancestors_of_region1:
            return current_region
      
        # Otherwise traverse up from region2 until we find a common ancestor
        while current_region in parent_map:
            current_region = parent_map[current_region]
            if current_region in ancestors_of_region1:
                return current_region
      
        # This line should never be reached given problem constraints
        return current_region

Alternative Clean Solution: A cleaner approach is to use a helper function that collects the full path from any region to root:

class Solution:
    def findSmallestRegion(
        self, regions: List[List[str]], region1: str, region2: str
    ) -> str:
        # Build parent map
        parent_map = {}
        for region_list in regions:
            parent_region = region_list[0]
            for child_region in region_list[1:]:
                parent_map[child_region] = parent_region
      
        # Helper function to get path from region to root
        def get_path_to_root(region):
            path = []
            current = region
            while current:
                path.append(current)
                current = parent_map.get(current)
            return path
      
        # Get paths for both regions
        path1 = set(get_path_to_root(region1))
      
        # Find first common ancestor
        current = region2
        while current:
            if current in path1:
                return current
            current = parent_map.get(current)