1257. Smallest Common Region


Problem Description

You are provided with a list that represents a hierarchy of regions where each list's first element is a region that includes all the following elements in the same list. Every region is considered to contain itself and any region it's listed with, where the first region is the largest and it is followed by regions it includes in descending order of size.

Now, you are given two specific regions, region1 and region2, and your task is to find the smallest common region that contains both of these regions.

Imagine a scenario where you have regions defined in a hierarchical manner, like in a geographical context—continents include countries, countries include states, states include cities, and so on. If given two cities, you must find the smallest state or country that includes both cities.

Note that for any region r3 included in r1, there will be no other r2 that includes r3. This simplifies the problem, ensuring that the tree of regions is well-defined and does not have any overlapping or conflicting ownership. The problem guarantees that there is always a smallest common region that exists for any two given regions.

Intuition

To arrive at the solution, we need to identify the hierarchy or the path of parents from each region to the top-most region in the hierarchy. Once we have the path for both regions, we can traverse these paths to find the smallest common region, which will be the first common ancestor.

We start by creating a map m that holds the parent-child relationship, where every region except the very first has a corresponding parent region that includes it—this constructs a map that resembles a tree.

Consider this tree as a family tree, where every person apart from the family's progenitor has a parent. region1 and region2 then become two family members, and we are looking for their closest common ancestor.

We populate a set s with ancestors of region1 by following the parent links up the hierarchy. Then, we start at region2 and move up its ancestral line until we encounter the first region already present in the set s, which will be the least common ancestor. If region2 or any of its ancestors do not appear in the set s, then region1 itself is the smallest region (this can only happen if region1 is the top-most region).

The use of the set ensures that we can efficiently check whether the region is a common ancestor, and iterating up the ancestral lines ensures we find the smallest such region containing both given regions.

Learn more about Tree, Depth-First Search and Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution follows a direct approach using a map and a set, which are simple yet powerful data structures in Python. Here's a step-by-step breakdown of the implementation based on the provided code:

  1. Create a map m to store the parent-child relationships. After processing all the regions' lists, m will contain a mapping where the key is a 'child' region, and the value is its immediate 'parent' region. This is achieved with a nested loop: the outer loop iterates over each list of regions, and the inner loop (starting from the second element) maps each region to its 'parent', which is the first element in the current list.

    1m = {}
    2for region in regions:
    3    for r in region[1:]:
    4        m[r] = region[0]
  2. Instantiate a set s, which will hold all the ancestors of region1. We then traverse up from region1 to the top-most ancestor (which will be a region with no parent in map m). As we traverse, we populate the set with each ancestor, creating a pathway from region1 to its top-most ancestor.

    1s = set()
    2while m.get(region1):
    3    s.add(region1)
    4    region1 = m[region1]
  3. Starting with region2, the code checks if region2 or any of its ancestors are in the set s, which would indicate a common ancestor has been found.

    1while m.get(region2):
    2    if region2 in s:
    3        return region2
    4    region2 = m[region2]
  4. If region2 itself or one of its ancestors was not in set s, then the loop stops once region2 becomes a region without a parent, which, as mentioned before, can only be the top-most ancestor (the very first region). In such a case, region1 had to be the top-most ancestor, and it's returned as the smallest region that contains both region1 and region2.

The implementation uses hashmap and hashset data structures, as map m and set s respectively, which facilitate the efficient lookup in constant time, O(1), for checking the presence of ancestors and mapping children to parents. This is how the Python dictionary and set are generally implemented.

This approach is efficient in terms of time complexity because it has to process each region only once when creating the map, which is O(N) where N is the total number of regions, and then the ancestral path for both regions, each being at most O(H) where H is the height of the hierarchy. Therefore, the overall complexity is O(N + H). The space complexity is O(N) for storing the map and the set of ancestors for region1.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Example Walkthrough

Let's illustrate the solution approach with an example. Suppose we have five regions arranged in the following hierarchy:

1[
2 ["Earth", "North America", "United States"],
3 ["United States", "California"],
4 ["United States", "New York"],
5 ["California", "Los Angeles"],
6 ["New York", "New York City"]
7]

And we are given two regions to find the smallest common region for: region1 = "Los Angeles" and region2 = "New York City".

  1. First, we create the map m listing each child's parent. It looks like this after processing the lists:

    1m = {
    2    "North America": "Earth",
    3    "United States": "North America",
    4    "California": "United States",
    5    "New York": "United States",
    6    "Los Angeles": "California",
    7    "New York City": "New York"
    8}
  2. Next, we add all ancestors of region1 ("Los Angeles") into the set s. We follow up the hierarchy from "Los Angeles" to "California", and then to "United States", which is an ancestor to both "California" and "New York":

    1s = set(["Los Angeles", "California", "United States"])
  3. After this, we check if region2 ("New York City") or any of its ancestors are in set s. We start with "New York City", whose parent is "New York", and then the parent of "New York" is "United States" which is in s. Thus, we find that "United States" is the smallest common region for "Los Angeles" and "New York City":

    1# "New York City" is not in s
    2# "New York"'s parent is "United States" which is in s
    3smallest_common_region = "United States"
  4. Now we have the result: the smallest common region containing both "Los Angeles" and "New York City" is "United States".

The example confirms our approach, showing how it finds the least common ancestor efficiently by constructing a map to represent the hierarchy and then using a set to track the ancestors of one region to compare with the ancestral line of the other region.

Not Sure What to Study? Take the 2-min Quiz:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Python Solution

1class Solution:
2    def findSmallestRegion(self, regions, region1, region2):
3        # Create a dictionary to map each region to its parent region.
4        parent_map = {}
5        for region in regions:
6            # region[0] is the parent region, and the rest are the child regions.
7            for child_region in region[1:]:
8                parent_map[child_region] = region[0]
9      
10        # A set to store all the ancestors of region1.
11        ancestors = set()
12        # Loop to find all ancestors of region1 and add them to the set.
13        while region1 in parent_map:
14            ancestors.add(region1)
15            # Move to the parent region.
16            region1 = parent_map[region1]
17      
18        # Loop to traverse the ancestors of region2.
19        while region2 in parent_map:
20            # Check if the current region2 is also an ancestor of region1.
21            if region2 in ancestors:
22                # If it is, we have found the smallest common region.
23                return region2
24            # Move to the parent region of region2.
25            region2 = parent_map[region2]
26      
27        # If there is no common ancestor in the set, the smallest common
28        # region is the topmost ancestor of region1.
29        return region1
30

Java Solution

1class Solution {
2    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
3        // Create a map to store each region's immediate parent region
4        Map<String, String> parentMap = new HashMap<>();
5        // Iterate through the list of regions to fill the parentMap
6        for (List<String> region : regions) {
7            for (int i = 1; i < region.size(); i++) {
8                // Map each child (i > 0) to its parent (0th element)
9                parentMap.put(region.get(i), region.get(0));
10            }
11        }
12      
13        // Initialize a set to keep track of all ancestors of region1
14        Set<String> ancestors = new HashSet<>();
15        // Go up the hierarchy of regions from region1, adding each to the ancestor set
16        while (parentMap.containsKey(region1)) {
17            ancestors.add(region1);
18            region1 = parentMap.get(region1); // Move to the parent region
19        }
20      
21        // Start from region2 and move up the hierarchy until you find a common ancestor
22        while (parentMap.containsKey(region2)) {
23            if (ancestors.contains(region2)) {
24                // If region2 or any of its ancestors is in the ancestors set, we've found the smallest common region
25                return region2;
26            }
27            region2 = parentMap.get(region2); // Move to the parent region
28        }
29      
30        // If no common ancestor is found while traversing from region2, return the highest ancestor of region1
31        return region1;
32    }
33}
34

C++ Solution

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5
6class Solution {
7public:
8    // Function to find the smallest common region between region1 and region2
9    std::string findSmallestRegion(std::vector<std::vector<std::string>>& regions, 
10                                   std::string region1, std::string region2) {
11        // Create a map to store the immediate parent for each region
12        std::unordered_map<std::string, std::string> parentMap;
13      
14        // Fill in the parent map with each region's parent
15        for (const auto& region : regions) {
16            for (size_t i = 1; i < region.size(); ++i) {
17                parentMap[region[i]] = region[0];
18            }
19        }
20      
21        // Create a set to store the ancestors of region1
22        std::unordered_set<std::string> ancestors;
23      
24        // Add all ancestors of region1 to the set
25        while (parentMap.count(region1)) {
26            ancestors.insert(region1);
27            region1 = parentMap[region1]; // Move up to the parent region
28        }
29      
30        // Find the first common ancestor of region2 which is in the ancestors set
31        while (parentMap.count(region2)) {
32            if (ancestors.count(region2)) {
33                return region2; // This is the closest common ancestor
34            }
35            region2 = parentMap[region2]; // Move up to the parent region
36        }
37      
38        // If there was no common ancestor found in the loop above,
39        // return the last ancestor of region1 which should be the root region
40        return region1;
41    }
42};
43

Typescript Solution

1type Region = string;
2type Regions = Region[][];
3
4// We use Map instead of unordered_map for parent mapping
5const parentMap = new Map<Region, Region>();
6
7/**
8 * Function to fill in the parent map with each region's parent.
9 */
10function fillParentMap(regions: Regions): void {
11    // Iterate through each list of regions
12    for (const regionList of regions) {
13        // The first region is the parent, the rest are its children
14        const parentRegion = regionList[0];
15        for (let i = 1; i < regionList.length; i++) {
16            const childRegion = regionList[i];
17            // Assign parent to the child region
18            parentMap.set(childRegion, parentRegion);
19        }
20    }
21}
22
23/**
24 * Function to find the smallest common region between region1 and region2.
25 */
26function findSmallestRegion(regions: Regions, region1: Region, region2: Region): Region {
27    // Fill the parent map before processing
28    fillParentMap(regions);
29
30    // Use Set to find the ancestors of region1
31    const ancestors = new Set<Region>();
32
33    // Add all ancestors of region1 to the set
34    while (parentMap.has(region1)) {
35        ancestors.add(region1);
36        region1 = parentMap.get(region1)!; // Move up to the parent region, using ! to assert that value is not undefined
37    }
38
39    // Find the first common ancestor of region2 which is in the ancestors set
40    while (parentMap.has(region2)) {
41        if (ancestors.has(region2)) {
42            return region2; // This is the closest common ancestor
43        }
44        region2 = parentMap.get(region2)!; // Move up to the parent region, using ! to assert that value is not undefined
45    }
46
47    // No common ancestor found in the loop above, return the root region instead
48    return region1;
49}
50
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?

Time and Space Complexity

The given Python code defines a function to find the smallest common region between region1 and region2.

  • Time complexity:

The time complexity of the first loop is O(N) where N is the total number of regions inside all the lists combined. This is because each region list is traversed exactly once, and each traversal takes O(K), where K is the number of sub-regions within the current region. Hence, the overall time for this loop is proportional to the total number of regions in all lists.

For the second and third while loops, the time complexity is O(H1 + H2), where H1 is the height of the region hierarchy (region tree) from region1 to the top, and H2 is the height from region2 to the top. In the worst-case scenario, this would be O(H) where H is the height of the tree.

Combining the two parts, the overall time complexity of the function can be expressed as O(N + H), assuming H can be considered smaller than N in a large dataset.

  • Space complexity:

The space complexity consists of the additional space used by the map m and set s. The map m has O(N) complexity as it contains all regions except the global root. The set s has O(H1) complexity in the worst case as it stores the path from region1 to the root.

Hence, the total space complexity of the function is O(N + H1). Since H1 is generally smaller compared to N, we can approximate the space complexity as O(N).

Learn more about how to find time and space complexity quickly.


Recommended Readings


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.


TA 👨‍🏫