Description
Given a list of regions where each list's first element contains the rest, find the smallest region that contains two given regions.
Examples
Input:
regions = [["Earth","North America","South America"],["North America","United States","Canada"]], region1 = "Canada", region2 = "United States"Output:
"North America"Explanation:
Common parent.
Input:
regions = [[1]], region1 = "Canada", region2 = "United States"Output:
"North America"Explanation:
Minimal case with a single region hierarchy.
Input:
regions = [["World","Asia","Europe","Africa"],["Asia","China","Japan","India"],["Europe","Germany","France"],["China","Beijing","Shanghai"]], region1 = "Beijing", region2 = "Germany"Output:
WorldExplanation:
Beijing is contained in China, which is contained in Asia, which is contained in World. Germany is contained in Europe, which is contained in World. The smallest region containing both Beijing and Germany is World, as they are in different continental branches of the hierarchy.
Constraints
- •
2 ≤ regions.length ≤ 10⁴