We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Common Region

Number: 1190

Difficulty: Medium

Paid? Yes

Companies: Airbnb, TikTok

Problem Description

You are given lists of regions where the first region in each list is a parent of all subsequent regions. A region is considered to contain itself. Given two regions, region1 and region2, the task is to determine the smallest (i.e., lowest in the hierarchy) region that contains both region1 and region2.

Key Insights

  • Treat each list as defining parent-child relationships, where the first element is the parent and the rest are children.
  • A mapping from child to parent can be constructed for efficient look-up.
  • Starting from each region, traverse upward using the parent mapping to get their full ancestry.
  • The smallest common region is the first common region encountered in both ancestry paths.
  • This is similar to finding the lowest common ancestor (LCA) in a tree.

Space and Time Complexity

Time Complexity: O(n + h), where n is the total number of regions and h is the height of the tree (worst-case traversal for ancestry). Space Complexity: O(n) for storing the parent mapping and O(h) for storing the ancestors of a given region.

Solution

The solution involves first building a mapping from each child region to its parent. Then, starting from region1, traverse up the parent chain and record all ancestors in a set. After that, traverse from region2 upward and check each ancestor against the set from region1. The first match will be the smallest common region containing both. This approach efficiently leverages a hash table (or dictionary) for constant-time lookups of ancestry, ensuring we quickly identify the common ancestor.

Code Solutions

# Python Solution
def findSmallestRegion(regions, region1, region2):
    # Build mapping from child region to its parent region
    parent = {}
    for region_list in regions:
        # the first region is the parent for the subsequent regions
        for i in range(1, len(region_list)):
            parent[region_list[i]] = region_list[0]
    
    # Build ancestry set for region1
    ancestors = set()
    while region1 in parent:
        ancestors.add(region1)
        region1 = parent[region1]
    ancestors.add(region1)  # add the top-most region
    
    # Traverse ancestry for region2 until an ancestor is found in region1's ancestry set
    while region2 not in ancestors:
        region2 = parent[region2]
    return region2

# Example usage:
regions = [["Earth","North America","South America"],
           ["North America","United States","Canada"],
           ["United States","New York","Boston"],
           ["Canada","Ontario","Quebec"],
           ["South America","Brazil"]]
print(findSmallestRegion(regions, "Quebec", "New York"))  # Output: "North America"
← Back to All Questions