Watch 4 video solutions for Smallest Common Region, a medium level problem involving Array, Hash Table, String. This walkthrough by Kelvin Chandra has 1,465 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1042 <= regions[i].length <= 201 <= regions[i][j].length, region1.length, region2.length <= 20region1 != region2regions[i][j], region1, and region2 consist of English letters.Problem Overview: You are given a hierarchy of regions where each list starts with a parent region followed by its children. Given two regions, return the smallest region that contains both. This is essentially a Lowest Common Ancestor problem on a region tree, but the tree is provided as grouped lists rather than explicit parent pointers.
Approach 1: Parent Map + Ancestor Set (Hash Table) (Time: O(n), Space: O(n))
Build a parent lookup table using a hash table. Iterate through each region list and map every child to its parent. Once you have parent pointers, walk from region1 up to the root and store every ancestor in a set. Then climb from region2 upward until you encounter a region already in that set. The first match is the smallest common region.
The key insight: once the hierarchy is converted into parent pointers, the problem becomes identical to finding the intersection of two ancestor chains. Hash lookups make ancestor checks constant time. This approach is simple, avoids building a full tree structure, and works directly with the input representation.
Approach 2: Explicit Tree + DFS LCA (Time: O(n), Space: O(n))
Another option is to construct an explicit tree using adjacency lists from the region hierarchy. The first element of each list is the parent; the rest become children nodes. Once the tree is built, run a depth‑first search to locate the lowest common ancestor of the two target regions.
During DFS, each recursive call returns whether it found region1 or region2 in its subtree. If two different branches report a match, the current node is the LCA. This mirrors classic LCA logic used in tree problems. The downside is extra code and recursion compared to the parent‑map technique.
Approach 3: Parent Map + Upward Traversal (Time: O(n), Space: O(n))
You can also compute full ancestor chains for both regions using the same parent map. Store the path from each region to the root, then compare the chains from the end (root side) until they diverge. The last common node is the answer. This approach avoids a hash set but requires storing two ancestor lists.
Recommended for interviews: The parent map + ancestor set solution is what most interviewers expect. It converts the hierarchy into a simple parent pointer structure and finds the first shared ancestor in linear time. Explaining the brute LCA idea on a tree shows conceptual understanding, but implementing the hash‑table approach demonstrates practical problem‑solving and clean reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Parent Map + Ancestor Set (Hash Table) | O(n) | O(n) | Best general solution; simple and efficient for hierarchy inputs |
| Explicit Tree + DFS LCA | O(n) | O(n) | Useful when practicing classic tree LCA techniques |
| Parent Map + Ancestor Path Comparison | O(n) | O(n) | Works when you prefer comparing ancestor chains instead of hash sets |