Smallest Common Region

Medium

Airbnb

3 views

Topics:

Graphs

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

For example, if regions = [["Earth", "North America", "USA"], ["Earth", "Asia", "China"]], then:

Earth is the common region of "North America" and "Asia".
Earth is the common region of "USA" and "China".

You are given the lists of regions regions where all regions are arranged in a hierarchy. Return the smallest common region that contains all of the given regions searchRegion1, searchRegion2.

Example 1:

Input: regions = [["Earth","North America","USA"],["Earth","Asia","China"]], searchRegion1 = "USA", searchRegion2 = "China"
Output: "Earth"

Example 2:

Input: regions = [["Earth", "North America", "USA"],["Earth", "Asia", "China"],["North America", "USA", "New York"]], searchRegion1 = "New York", searchRegion2 = "China"
Output: "Earth"

Example 3:

Input: regions = [["Earth", "North America", "USA"],["Earth", "Asia", "China"],["North America", "USA", "New York"]], searchRegion1 = "USA", searchRegion2 = "New York"
Output: "USA"

Constraints:

2 <= regions.length <= 10⁴
2 <= regions[i].length <= 10
All the regions are different.
searchRegion1 != searchRegion2
searchRegion1 and searchRegion2 are region names in the given regions.

Smallest Common Region

Medium

Airbnb

3 views

Topics:

Graphs

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

For example, if regions = [["Earth", "North America", "USA"], ["Earth", "Asia", "China"]], then:

Earth is the common region of "North America" and "Asia".
Earth is the common region of "USA" and "China".

You are given the lists of regions regions where all regions are arranged in a hierarchy. Return the smallest common region that contains all of the given regions searchRegion1, searchRegion2.

Example 1:

Input: regions = [["Earth","North America","USA"],["Earth","Asia","China"]], searchRegion1 = "USA", searchRegion2 = "China"
Output: "Earth"

Example 2:

Input: regions = [["Earth", "North America", "USA"],["Earth", "Asia", "China"],["North America", "USA", "New York"]], searchRegion1 = "New York", searchRegion2 = "China"
Output: "Earth"

Example 3:

Input: regions = [["Earth", "North America", "USA"],["Earth", "Asia", "China"],["North America", "USA", "New York"]], searchRegion1 = "USA", searchRegion2 = "New York"
Output: "USA"

Constraints:

2 <= regions.length <= 10⁴
2 <= regions[i].length <= 10
All the regions are different.
searchRegion1 != searchRegion2
searchRegion1 and searchRegion2 are region names in the given regions.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Will the input `regions` always form a valid tree structure, or could there be cycles or disconnected regions?
Are `region1` and `region2` guaranteed to exist within the `regions` structure? If not, what should I return?
Could a region be its own ancestor? In other words, could `region1` and `region2` be the same region, and if so, should I return that region?
What is the maximum depth of the region tree, and the maximum number of sub-regions for each region?
Are the region names guaranteed to be unique across all regions, or could the same name appear in multiple region lists?

Brute Force Solution

Approach

The brute force approach involves exploring every possible common region to find the smallest one. We essentially check all regions to see if they are ancestors of the given regions. We pick the smallest one that fits the requirement.

Here's how the algorithm would work step-by-step:

Start by considering each region as a potential common ancestor.
For each potential common ancestor, check if it is an ancestor of all the given regions.
To check if a region is an ancestor of another, trace the path from the second region upwards through its parent regions until you either find the first region or reach the root.
If the potential common ancestor is an ancestor of all the given regions, it's a valid common ancestor.
Keep track of all the valid common ancestors.
From all the valid common ancestors, choose the one that appears earliest in the hierarchy. This is the smallest common region.

Code Implementation

def smallest_common_region_brute_force(regions):
    parent_map = {}
    for region_list in regions:
        parent = region_list[0]
        for child in region_list[1:]:
            parent_map[child] = parent

    all_regions = set(parent_map.keys())
    for region_list in regions:
        all_regions.add(region_list[0])
    all_regions = list(all_regions)

    given_regions = [region_list[1:] for region_list in regions]
    given_regions = [region for sublist in given_regions for region in sublist]
    given_regions = list(set(given_regions))

    valid_common_ancestors = []
    for potential_ancestor in all_regions:
        is_common_ancestor = True
        for region in given_regions:
            if not is_ancestor(parent_map, potential_ancestor, region):
                is_common_ancestor = False
                break

        if is_common_ancestor:
            valid_common_ancestors.append(potential_ancestor)

    # We prioritize the valid ancestors
    if not valid_common_ancestors:
        return None

    return valid_common_ancestors[0]

def is_ancestor(parent_map, potential_ancestor, region):
    current_region = region
    while current_region in parent_map:
        if current_region == potential_ancestor:
            return True

        current_region = parent_map[current_region]

    # Need to check if the potential ancestor is the root
    return current_region == potential_ancestor

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the number of regions in the input list of regions, and m be the maximum depth (number of ancestor relationships to the root) in the region hierarchy. The algorithm iterates through each of the n regions as a potential common ancestor. For each potential common ancestor, it checks if it's an ancestor of all the other regions. Checking if one region is an ancestor of another takes at most m steps because we trace up the parent chain. Since we do this check for all n regions and for each, we may traverse m ancestors, the total time complexity is O(n*m).

Space Complexity

O(N) – The space complexity is primarily determined by the ancestor tracing process. In the worst-case scenario, to check if a potential common ancestor is indeed an ancestor of a given region, we might have to traverse a path from the region to the root, potentially visiting each node in the hierarchy. Thus, the depth of the hierarchy can be up to N where N is the number of regions (or nodes) in the hierarchy, requiring space to store this path information (either implicitly in the call stack during recursion, or explicitly in a data structure). Therefore, the space complexity is O(N).

Optimal Solution

Approach

To find the smallest common region, we can think of the regions as forming a tree-like structure where smaller regions are nested inside larger ones. The key idea is to find the paths from each of the given regions up to the root and then identify where these paths first intersect, which represents the smallest common region.

Here's how the algorithm would work step-by-step:

First, build a structure that clearly shows how each region is related to its parent region.
Then, for each of the regions we're given, trace a path upwards from that region towards the root region.
Record the path of regions visited from each input region to the root.
Next, find the first region that appears on all the paths you've recorded. This is the smallest region that contains all the input regions.
The first region found in all traced paths is the desired answer.

Code Implementation

def smallest_common_region(regions, region1, region2):
    parent_map = {}
    for region_list in regions:
        parent_region = region_list[0]
        for sub_region in region_list[1:]:
            parent_map[sub_region] = parent_region

    # Store the paths to the root for region1 and region2
    path_region1 = get_path_to_root(region1, parent_map)

    path_region2 = get_path_to_root(region2, parent_map)

    # Find the smallest common region
    for region in path_region1:
        if region in path_region2:
            return region

def get_path_to_root(region, parent_map):
    path = []
    while region in parent_map:
        path.append(region)
        region = parent_map[region]

    # Add the root region to the path
    path.append(region)

    #Reverse the path to start from the given region
    path.reverse()
    return path

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the total number of regions and m be the number of input regions we are finding the smallest common region for. Building the region-parent mapping takes O(n) time. Tracing the path from each of the m input regions to the root takes O(n) time per region in the worst case. Finding the intersection of these paths, again involves iterating through these paths, up to the root, which is also O(n) multiplied by the number of paths m. Thus the total time complexity is O(n*m).

Space Complexity

O(N) – The algorithm constructs a parent-child mapping of the regions, which uses O(N) space, where N is the total number of regions. Additionally, tracing paths from each input region to the root stores these paths, which in the worst case, could be of length N for each region, but since we're finding a common region, it would effectively be a maximum of N (number of regions) in auxiliary space. Thus, the dominant space usage is from the parent-child mapping and the path storage, both contributing to O(N) space complexity.

Edge Cases

Case	How to Handle
regions is null or empty	Return null or an empty string because there are no regions to process.
region1 or region2 is null or empty	Return null or an empty string as either of the regions not existing would invalidate the search for the lowest common ancestor.
region1 or region2 does not exist in the regions list	Return null or an empty string indicating that the provided regions are not valid.
region1 and region2 are the same	Return region1 (or region2) directly as it is the lowest common ancestor of itself.
One region is the ancestor of the other	Return the ancestor region since it is also the lowest common ancestor.
regions represents a disconnected graph (multiple trees)	The algorithm should still work as it searches upwards from each specified region until the common ancestor is found, processing each tree individually if disconnected.
Large number of regions leading to deep recursion/large parent map	Iterative approach with storing parents in a map ensures efficient execution and avoids recursion depth issues.
The regions list contains cycles, violating the tree-like structure assumption	The parent map construction should handle cycles by potentially overwriting parents during creation, resulting in an arbitrary but valid lowest common ancestor.