Smallest Common Region Leetcode Solution

Difficulty Level Medium
Frequently asked in AirbnbViews 2621

Problem Statement

Smallest Common Region Leetcode Solution – 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 and region2, return 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 is guaranteed the smallest region exists.

Example

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"

Explanation:

Since the region “North America” is the Smallest region that contains both “Quebec” and “New York” , we return “North America”.

Input:

 regions = [["Earth", "North America", "South America"],["North America", "United States", "Canada"],["United States", "New York", "Boston"],["Canada", "Ontario", "Quebec"],["South America", "Brazil"]], region1 = "Canada", region2 = "South America"

Output:

 "Earth"

Explanation :

Since the region “Earth” is the Smallest region that contains both “Canada” and “South America”, we return “Earth”.

Approach

Idea:

We can think of this problem as a graph problem, in every list of regions the first region is the largest one containing all the other smaller elements that are, it will act as a parent node for all the regions in a particular list.

If we carefully look at this graph, we can clearly see that this graph is a tree as the larger region only can contain the smaller element, not vice versa. So there will not be any bidirectional edges.  Also, there will not be any duplicate region present as it is given in the question.

Since, we have to find the smallest region containing both the given regions, the problem boils down to finding the LCA of two nodes.

Algorithm:

Step -1  Build a Hashmap to store the parent of every child.

Step-2 Use a Hashmap to store the ancestor history of the region1.

Step-3 Traverse through the ancestor history of region2 and if found that this was also in the path of region1, then that’s our smallest common region between region1 and region2.

Code for Smallest Common Region

C++ Code

class Solution {
public:
    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
        
        unordered_map<string,string> parent;
        // To store the parent of every node.
        
        for(auto vc : regions){
            for(int i=1;i<vc.size();i++){
                parent[vc[i]] = vc[0];
                // Since first index is parent of all other nodes in the list.
            }
        }
        
        unordered_map<string,int> vis;
        //To keep track of all the nodes in the path from region1 to root.
        
        while(region1.size()!=0){
            vis[region1] = 1;
            region1 = parent[region1];
            // Making all the nodes visited.
        }
        
        while(!vis.count(region2)){
            region2 = parent[region2];
        }
        //while the node in the path is not visited previosly keep moving up, towards root.
        
        
        return region2;
        //We have found a common region.
    }
};

Java Code

class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2){
        
        Map<String, String> parents = new HashMap<>();
        // To store the parent of every node.
        
        Set<String> ancestryHistory = new HashSet<>();
        //To keep track of all the nodes in the path from region1 to root.
        
        for (List<String> region : regions)
            for (int i = 1; i < region.size(); ++i){
                // Since first index is parent of all other nodes in the list.   
                parents.put(region.get(i), region.get(0));
            }
        
        
        while (region1 != null) {
            ancestryHistory.add(region1);
            region1 = parents.get(region1);
            // Making all the nodes visited.
        }
        
        //while the node in the path is not visited previosly keep moving up, towards root.
        while (!ancestryHistory.contains(region2))
            region2 = parents.get(region2);
        
        return region2;
        //We have found a common region.
    }
}

Complexity Analysis For Smallest Common Region Leetcode Solution

Time Complexity

We are traversing the all regions to keep track of the parent and then, moving upwards in a tree, So the overall time complexity is O(N), where N is the total number of regions.

Space Complexity

We are using extra space for storing the parent of each node and extra space for the visited map. So the overall Space complexity is also O(N),  where N is the total number of regions.

Translate »