Smallest Common Region

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 region1region2, find out the smallest region that contains both of them. If you are given regions r1r2 and r3 such that r1 includes r3, it is guaranteed there is no r2 such that r2 includes r3.

It’s guaranteed the smallest region exists.

Example 1:

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"

Constraints:

  • 2 <= regions.length <= 10^4
  • region1 != region2
  • All strings consist of English letters and spaces with at most 20 letters.

This problem is the same as finding the lowest common ancestor of two nodes in a Binary Tree.

1. Build family tree from offsprings to their parents;

2. Use a HashSet to construct ancestry history of region1;

3. Retrieve ancestry of region2 by family tree till find the first common ancestry in ancestry history of region1.

class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, 
              String region2) {
        
        Map<String, String> regionMap = new HashMap<>();
        String root = regions.get(0).get(0);
        regionMap.put(root, null);
        for(List<String> regionList : regions){
            String currentParent = regionList.get(0);
            for(int i = 1 ; i < regionList.size() ; i++){
                regionMap.put(regionList.get(i), currentParent);
            }
        }
        Set<String> seen = new HashSet<>();
        while(region1 != null){
            seen.add(region1);
            region1 = regionMap.get(region1);
        }
        String lca = null;
        while(region2 != null){
            if(seen.contains(region2)){
                lca = region2;
                break;
            }
            region2 = regionMap.get(region2);
        }
        return lca;
    }
}

Time & space: O(n), where n is the the number of totoal regions.

Categories: Graph

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s