# 1257. Smallest Common Region

You are given some lists of regions where the first region of each list includes all other regions in that list.

Naturally, if a region X contains another region Y then X is bigger than Y.

Given two regions region1, region2, find out the smallest region that contains both of them.

If you are given regions r1, r2 and r3 such that r1 includes r3, it is guaranteed there is no r2 such that r2 includes r3.

It's guaranteed the smallest region exists.

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"

# Solution

Approach 1: problem: find lowest common ancester in a tree.

# Code (Python)

Approach 1:

class Solution:
    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
        # problem: find lowest common ancester in a tree
        parents = {}
        for region in regions:
            for item in region[1:]:
                parents[item] = region[0]
        
        common_region = ''
        region1_zoom, region2_zoom = self._zoom(region1, parents), self._zoom(region2, parents)
        for r1, r2 in zip(reversed(region1_zoom), reversed(region2_zoom)):
            if r1 == r2:
                common_region = r1
            else:
                return common_region
        
        return common_region
    
    def _zoom(self, region, parents):
        result = [region]
        while result[-1] in parents:
            result.append(parents[result[-1]])
        return result

# Code (C++)

Approach 1:

Approach 2: