Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1257.html

1257. Smallest Common Region

Level

Medium

Description

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, region2, find out 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’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.

Solution

Use a map to store each region and its parent. Say region X is region Y’s parent if region X directly includes region Y. Also say region X is region Z’s ancestor if there exists a path such that X -> X₁ -> X₂ -> … -> X_n -> X_n+1 -> … -> Z where “->” represents a parent-child relation (that is to say, X_n is a parent of X_n+1).

Use a set to store region1 and all its ancestors. Then for region2, find the lowest ancestor that is in the set, which is the lowest ancestor of region1. Return the lowest ancestor.

• Java
• Python
• C++
• Go

• class Solution {
      public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
          Map<String, String> map = new HashMap<String, String>();
          for (List<String> list : regions) {
              int size = list.size();
              String first = list.get(0);
              for (int i = 1; i < size; i++)
                  map.put(list.get(i), first);
          }
          Set<String> set = new HashSet<String>();
          String str1 = region1;
          while (str1 != null) {
              set.add(str1);
              str1 = map.get(str1);
          }
          String str2 = region2;
          while (!set.contains(str2))
              str2 = map.get(str2);
          return str2;
      }
  }
  

• class Solution:
      def findSmallestRegion(
          self, regions: List[List[str]], region1: str, region2: str
      ) -> str:
          m = {}
          for region in regions:
              for r in region[1:]:
                  m[r] = region[0]
          s = set()
          while m.get(region1):
              s.add(region1)
              region1 = m[region1]
          while m.get(region2):
              if region2 in s:
                  return region2
              region2 = m[region2]
          return region1
  
  
  

• class Solution {
  public:
      string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
          unordered_map<string, string> m;
          for (auto& region : regions)
              for (int i = 1; i < region.size(); ++i)
                  m[region[i]] = region[0];
          unordered_set<string> s;
          while (m.count(region1)) {
              s.insert(region1);
              region1 = m[region1];
          }
          while (m.count(region2)) {
              if (s.count(region2)) return region2;
              region2 = m[region2];
          }
          return region1;
      }
  };
  

• func findSmallestRegion(regions [][]string, region1 string, region2 string) string {
  	m := make(map[string]string)
  	for _, region := range regions {
  		for i := 1; i < len(region); i++ {
  			m[region[i]] = region[0]
  		}
  	}
  	s := make(map[string]bool)
  	for region1 != "" {
  		s[region1] = true
  		region1 = m[region1]
  	}
  	for region2 != "" {
  		if s[region2] {
  			return region2
  		}
  		region2 = m[region2]
  	}
  	return region1
  }
  

All Problems

All Solutions