Problem statement

https://leetcode.com/problems/smallest-common-region/

Solution

In this problem we just need to find LCA of two nodes in graph and only for one pair. So, what we can do is just create parent links and first traverse from r1 to root and save in in path. Then we start with r2 and see when we have LCA.

Complexity

Time complexity is O(n), space potentially O(n) as well.

Code

class Solution:
    def findSmallestRegion(self, R, r1, r2):
        G, path = defaultdict(list), {r1}
        for r in R:
            for i in r[1:]:
                G[i] = r[0]
                
        while r1 in G:
            r1 = G[r1]
            path.add(r1)
            
        while r2 not in path:
            r2 = G[r2]
            
        return r2