Smallest Common Region

The problem is about finding the smallest region that contains both region1 and region2, given a list of regions where each region may contain other regions.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
        parent = {}
        for region in regions:
            for subregion in region[1:]:
                parent[subregion] = region[0]

        path_to_region1 = set()
        while region1:
            path_to_region1.add(region1)
            region1 = parent.get(region1)

        while region2 not in path_to_region1:
            region2 = parent[region2]

        return region2

Explanation

1. Creating Parent Map: We start by creating a mapping of each subregion to its parent region using the parent dictionary. We iterate through the regions, and for each subregion, we map it to the parent region (first element in the list).

2. Finding Path to Region1: Next, we need to find the path from region1 to the root region (e.g., “Earth”). We use a set path_to_region1 to store all the regions in this path, including region1 itself.

3. Finding Smallest Common Region: Finally, we use the path from step 2 to find the smallest common region that contains both region1 and region2. We iterate through the parents of region2 until we find a region that is also in the path to region1. This common region is the smallest region that contains both region1 and region2, so we return it.