---
link: https://leetcode.com/problems/smallest-common-region/
tags: array, matrix, tree, adjacency list, medium
---

# 1257. Smallest Common Region

## Question

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`. Also by definition a region X contains itself.

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"

**Constraints:**

- `2 <= regions.length <= 10^4`
- `region1 != region2`
- All strings consist of English letters and spaces with at most 20 letters.

## Solution: Python

class Solution(object):
    def findSmallestRegion(self, regions, region1, region2):
        """
        :type regions: List[List[str]]
        :type region1: str
        :type region2: str
        :rtype: str
        """
        root = self.constructNaryTree(regions)
        self.smallest_region = None
        self.helper(root, region1, region2)
        return self.smallest_region.region if self.smallest_region else None
    
    def helper(self, node, region1, region2):
        if node is None:
            return False, False
        
        found_region_1, found_region_2 = node.region == region1, node.region == region2
        
        if found_region_1 and found_region_2:
                self.smallest_region = node
                return False, False
        
        for subregion in node.subregions.values():
            subregion_found_region_1, subregion_found_region_2 = self.helper(
                subregion,
                region1,
                region2
            )
            found_region_1 = found_region_1 or subregion_found_region_1
            found_region_2 = found_region_2 or subregion_found_region_2
            
            if found_region_1 and found_region_2:
                self.smallest_region = node
                return False, False
        
        return found_region_1, found_region_2
    
    def constructNaryTree(self, regions):
        nodes = {}
        root = None
        
        for region in regions:
            key = region[0]
            node = nodes.get(key, TreeNode(region=key))
            nodes[key] = node
            
            if root is None:
                root = node
            
            for idx in xrange(1, len(region)):
                subregion_node = nodes.get(region[idx], TreeNode(region=region[idx]))
                nodes[region[idx]] = subregion_node
                node.subregions[region[idx]] = subregion_node
        
        return root

class TreeNode():
    def __init__(self, region):
        self.region = region
        self.subregions = {}
    
    def __str__(self):
        return str(self.__dict__)
        
# solution = Solution()
# regions = [["Earth","North America","South America"],["North America","United States","Canada"],["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]]
# region_1 = "Quebec"
# region_2 = "New York"
# print solution.findSmallestRegion(regions, region_1, region_2)