Leetcode 1257. Smallest Common Region
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:
- Create a parent map associating each region with its parent region.
- Create a set of ancestors and insert all ancestors of
region1
in it. - Traverse through
region2
and its ancestors until you encounter the first ancestor which is also an ancestor toregion1
. This is the smallest region enclosing bothregion1
andregion2
.
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:
- 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"]]
. Letregion1 = "Quebec"
andregion2 = "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"
- Now consider
regions = [["Earth","North America","South America"],["North America","United States","Canada"],["United States","New York","Boston"],["Canada","Ontario","Quebec"],["South America","Brazil"]]
. Letregion1 = "Brazil"
andregion2 = "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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.