Problem of The Day: Smallest Common Region

Problem Statement

Intuition

The problem can be framed as finding the lowest common ancestor (LCA) of two regions in a tree-like structure, where each node represents a region, and its child nodes represent the regions within it. This suggests a recursive approach where we explore the region hierarchy to find the smallest common region.

Approach

1. Graph Representation: First, we represent the regions as a directed graph where each region points to its subregions.
2. Recursive Search for LCA: We define a recursive function to find the LCA. Starting from the root region, for each subregion, we check if it contains either of the two regions (region1 or region2). If a region contains both target regions in its subtree, it becomes the lowest common ancestor.
3. Handling Base Cases: The base case for the recursion is when the current region is one of the target regions (region1 or region2), which is returned upwards through the recursive calls.
4. Track the Result: As we traverse the graph, we track whether we’ve found a region that satisfies the condition of being the LCA.

Complexity

• Time complexity: \(O(n)\), where \(n\) is the number of regions. This is because we traverse the entire graph once to construct it and then traverse it again in a depth-first manner to find the LCA.

• Space complexity: \(O(n)\), where \(n\) is the number of regions. This is due to the space used by the recursion stack and the adjacency list representation of the graph.

Code

class Solution:
    def __init__(self):
        self.ans = None

    def find_lowest_common_ancestor(self, graph, q, p, curr):
        foundedRegions = []
        found = curr == q or curr == p
        for node in graph[curr]:
            foundedRegions.append(self.find_lowest_common_ancestor(graph, q, p, node))

        if (found and any(foundedRegions)) or (sum(foundedRegions) >= 2):
            self.ans = curr

        return any(foundedRegions) or found

    def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
        graph = defaultdict(list)
        for region in regions:
            graph[region[0]] = region[1:]
        self.find_lowest_common_ancestor(graph, region1, region2, regions[0][0])
        return self.ans

Editorial

Approach: Lowest Common Ancestor of a Generic Tree

class Solution:
    # Function to return a list representing the path from the root node
    # to the current node.
    def fetch_path_for_region(self, curr_node, child_parent_map):
        path = []
        # Start by adding the current node to the path.
        path.append(curr_node)

        # Traverse upwards through the tree by finding the parent of the
        # current node. Continue until the root node is reached.
        while curr_node in child_parent_map:
            parent_node = child_parent_map[curr_node]
            path.append(parent_node)
            curr_node = parent_node

        # Reverse the path so that it starts from the root and
        # ends at the given current node.
        path.reverse()
        return path

    def findSmallestRegion(
        self, regions: List[List[str]], region1: str, region2: str
    ) -> str:
        # Dictionary to store (child -> parent) relationships for each region.
        child_parent_map = {}

        # Populate the 'child_parent_map' using the provided 'regions' list.
        for region_array in regions:
            parent_node = region_array[0]
            for i in range(1, len(region_array)):
                child_parent_map[region_array[i]] = parent_node

        # Store the paths from the root node to 'region1' and 'region2'
        # nodes in their respective lists.
        path1 = self.fetch_path_for_region(region1, child_parent_map)
        path2 = self.fetch_path_for_region(region2, child_parent_map)

        i, j = 0, 0
        lowest_common_ancestor = ""
        # Traverse both paths simultaneously until the paths diverge.
        # The last common node is the lowest common ancestor.
        while i < len(path1) and j < len(path2) and path1[i] == path2[j]:
            lowest_common_ancestor = path1[i]
            i += 1
            j += 1

        # Return the lowest common ancestor of 'region1' and 'region2'.
        return lowest_common_ancestor

• time: O(m * n)
• space: O(m * n)