Problem Explanation

In this problem, we are given a list of regions with each region being a list itself, where the first element represents a bigger region containing all other regions mentioned in the list. We are also given two separate regions region1 and region2 and we have to find out the smallest region which contains both region1 and region2.

For example, consider the regions as regions = [["Earth","North America","South America"],["North America","United States","Canada"],["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]] and region1 = "Quebec", region2 = "New York". For these inputs, the smallest region that contains both region1 and region2 would be "North America" and hence, the output would be "North America".

The constraints on the problem ensure that we don't have overlapping regions i.e., if a region r1 includes r3, there won't be a different region r2 that includes r3.

Problem Solution's Approach

The solution to this problem is based on the concept of graphs and depth-first search (DFS) algorithm. It makes use of parent pointers and set data structure to keep track of ancestors of a node (or a region).

At high level, the algorithm is as follows:

1. Create a parent map associating each region with its parent region.
2. Create a set of ancestors and insert all ancestors of region1 in it.
3. Traverse through region2 and its ancestors until you encounter the first ancestor which is also an ancestor to region1. This is the smallest region enclosing both region1 and region2.

To get a better understanding, let's use the previous example of regions. First, the parent map would look something like this after step 1.

1
2plaintext
3{
4 "North America" : "Earth",
5 "South America" : "Earth",
6 "United States" : "North America",
7 "Canada" : "North America",
8 "New York" : "United States",
9 "Boston" : "United States",
10 "Ontario" : "Canada",
11 "Quebec" : "Canada",
12 "Brazil" : "South America"
13}

Next, for region1 = "Quebec", the ancestors set after step 2 would look like this:

1
2plaintext
3{ "Quebec", "Canada", "North America", "Earth" }

Then, as per step 3, we start traversing through the ancestors of region2 = "New York". The smallest region containing both region1 and region2 would be "North America".

Let's proceed with implementations in different languages.

Python Solution

1
2python
3class Solution:
4    def findSmallestRegion(self, regions, region1, region2):
5        parent, ancestors = {}, set()  
6        
7        for region in regions: 
8            for i in range(1, len(region)): 
9                parent[region[i]] = region[0] 
10        
11        while region1:
12            ancestors.add(region1)
13            region1 = parent[region1] 
14        
15        while region2 not in ancestors:
16            region2 = parent[region2]
17        
18        return region2

Java Solution

1
2java
3public class Solution {
4    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
5        Map<String, String> parent = new HashMap<>();
6        Set<String> ancestors = new HashSet<>();
7
8        for (List<String> region : regions)
9            for (int i = 1; i < region.size(); i++)
10                parent.put(region.get(i), region.get(0));
11        
12        while (region1 != null) {
13            ancestors.add(region1);
14            region1 = parent.get(region1);
15        }
16
17        while (!ancestors.contains(region2))
18            region2 = parent.get(region2);
19        
20        return region2;
21    }
22}

JavaScript Solution

1
2javascript
3class Solution {
4    findSmallestRegion(regions, region1, region2) {
5        const parent = {};
6        const ancestors = new Set();
7        
8        for (let region of regions)
9            for (let i = 1; i < region.length; i++)
10                parent[region[i]] = region[0];
11        
12        while (region1) {
13            ancestors.add(region1);
14            region1 = parent[region1];
15        }
16
17        while (!ancestors.has(region2))
18            region2 = parent[region2];
19        
20        return region2;
21    }
22}

C++ Solution

1
2cpp
3class Solution {
4public:
5    string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
6        unordered_map<string, string> parent;
7        unordered_set<string> ancestors;
8
9        for (auto& region : regions)
10            for (int i = 1; i < region.size(); i++)
11                parent[region[i]] = region[0];
12
13        while (region1 != "") {
14            ancestors.insert(region1);
15            region1 = parent[region1];
16        }
17
18        while (ancestors.count(region2) == 0)
19            region2 = parent[region2];
20        
21        return region2;
22    }
23};

C# Solution

1
2csharp
3public class Solution {
4    public string FindSmallestRegion(IList<IList<string>> regions, string region1, string region2) {
5        Dictionary<string, string> parent = new Dictionary<string, string>();
6        HashSet<string> ancestors = new HashSet<string>();
7
8        foreach (var region in regions)
9            for (int i = 1; i < region.Count; i++)
10                parent[region[i]] = region[0];
11
12        while (region1 != null) {
13            ancestors.Add(region1);
14            region1 = parent.ContainsKey(region1) ? parent[region1] : null;
15        }
16
17        while (!ancestors.Contains(region2))
18            region2 = parent[region2];
19        
20        return region2;
21    }
22}

In the above solutions, we first form the parent mapping for all regions by iterating over the given regions. Then we add all of the ancestors of region1 into the set data structure. After that, we start from region2 and go up its ancestor tree until we find an ancestor that is also an ancestor of region1 and return that region.## Time and Space Complexity Analysis

The time complexity of the above solutions is O(N), where N is the total number of given regions. This is because in the worst case, the algorithm iterates over all regions twice. First iteration is for forming the parent map. The second iteration is for finding the common ancestor, which involves traversing up the ancestor tree for region1 and region2, which in worst case scenario can include all regions.

The space complexity of these solutions is also O(N). We use two additional data structures, parent map and ancestors set. The parent map keeps track of the parent region for every region, hence can have as many entries as there are regions. The ancestors set will keep all the ancestry of region1, and In the worst case scenario, a region can have all other regions as its ancestry, and hence the ancestors set can have N-1 entries. So, the space complexity of these solutions is linear.

These are clearly optimal solutions for the problem since we have to at least look at all regions once. The space required is also optimal as we need to keep track of parent of each region separately, and also need to know the ancestry of region1. Non-linear approaches in terms of time or space do not seem possible for this problem.

Testing

Let's try out the python solution with a couple of different test cases to validate it:

1. Consider the regions as regions = [["Earth","North America","South America"],["North America","United States","Canada"],["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]]. Let region1 = "Quebec" and region2 = "New York". For these inputs, the solution will return 'North America'.

1
2python
3s = Solution()
4print(s.findSmallestRegion([["Earth","North America","South America"],["North America","United States","Canada"],["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]], "Quebec", "New York"))
5#Expected output: "North America"

2. Now consider regions = [["Earth","North America","South America"],["North America","United States","Canada"],["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]]. Let region1 = "Brazil" and region2 = "Quebec". For these inputs, the solution will return 'Earth'.

1
2python
3s = Solution()
4print(s.findSmallestRegion([["Earth","North America","South America"],["North America","United States","Canada"],["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]], "Brazil", "Quebec"))
5#Expected output: "Earth"

You can test the Java, JavaScript, C++, and C# solutions similarly.