LeetCode 1257. Smallest Common Region Solution in Java, C++, Python & More | Explanation + Code

Description

You are given some lists of regions where the first region of each list directly contains all other regions in that list.

If a region x contains a region y directly, and region y contains region z directly, then region x is said to contain region z indirectly. Note that region x also indirectly contains all regions indirectly containd in y.

Naturally, if a region x contains (either directly or indirectly) another region y, then x is bigger than or equal to y in size. Also, by definition, a region x contains itself.

Given two regions: region1 and region2, return the smallest region that contains both of them.

It is 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"

Example 2:

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"

 

Constraints:

• 2 <= regions.length <= 104
• 2 <= regions[i].length <= 20
• 1 <= regions[i][j].length, region1.length, region2.length <= 20
• region1 != region2
• regions[i][j], region1, and region2 consist of English letters.
• The input is generated such that there exists a region which contains all the other regions, either directly or indirectly.
• A region cannot be directly contained in more than one region.

Solutions

Solution 1: Hash Table

We can use a hash table g to store the parent region of each region. Then, starting from region1, we keep moving upwards to find all its parent regions until the root region, and store these regions in the set s. Next, starting from region2, we keep moving upwards to find the first region that is in the set s, which is the smallest common region.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the region list regions.

PythonJavaC++GoTypeScriptRust

class Solution: def findSmallestRegion( self, regions: List[List[str]], region1: str, region2: str ) -> str: g = {} for r in regions: x = r[0] for y in r[1:]: g[y] = x s = set() x = region1 while x in g: s.add(x) x = g[x] x = region2 while x in g and x not in s: x = g[x] return x(code-box)

class Solution { public String findSmallestRegion(List<List<String>> regions, String region1, String region2) { Map<String, String> g = new HashMap<>(); for (var r : regions) { String x = r.get(0); for (String y : r.subList(1, r.size())) { g.put(y, x); } } Set<String> s = new HashSet<>(); for (String x = region1; x != null; x = g.get(x)) { s.add(x); } String x = region2; while (g.get(x) != null && !s.contains(x)) { x = g.get(x); } return x; } }(code-box)

class Solution { public: string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) { unordered_map<string, string> g; for (const auto& r : regions) { string x = r[0]; for (size_t i = 1; i < r.size(); ++i) { g[r[i]] = x; } } unordered_set<string> s; for (string x = region1; !x.empty(); x = g[x]) { s.insert(x); } string x = region2; while (!g[x].empty() && s.find(x) == s.end()) { x = g[x]; } return x; } };(code-box)

func findSmallestRegion(regions [][]string, region1 string, region2 string) string { g := make(map[string]string) for _, r := range regions { x := r[0] for _, y := range r[1:] { g[y] = x } } s := make(map[string]bool) for x := region1; x != ""; x = g[x] { s[x] = true } x := region2 for g[x] != "" && !s[x] { x = g[x] } return x }(code-box)

function findSmallestRegion(regions: string[][], region1: string, region2: string): string { const g: Record<string, string> = {}; for (const r of regions) { const x = r[0]; for (const y of r.slice(1)) { g[y] = x; } } const s: Set<string> = new Set(); for (let x: string = region1; x !== undefined; x = g[x]) { s.add(x); } let x: string = region2; while (g[x] !== undefined && !s.has(x)) { x = g[x]; } return x; }(code-box)

use std::collections::{HashMap, HashSet}; impl Solution { pub fn find_smallest_region(regions: Vec<Vec<String>>, region1: String, region2: String) -> String { let mut g: HashMap<String, String> = HashMap::new(); for r in &regions { let x = &r[0]; for y in &r[1..] { g.insert(y.clone(), x.clone()); } } let mut s: HashSet<String> = HashSet::new(); let mut x = Some(region1); while let Some(region) = x { s.insert(region.clone()); x = g.get(&region).cloned(); } let mut x = Some(region2); while let Some(region) = x { if s.contains(&region) { return region; } x = g.get(&region).cloned(); } String::new() } }(code-box)