Smallest Common Region
Smallest Common Region is a medium trees & bst problem solved with the lca pattern.
The best approach, optimal (parent map and ancestor set), runs in O(T) time and O(T) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (climb by rescanning the lists) up.
Problem
You are given a list of region lists. In each list regions[i], the first name is a region that directly contains every other name in that list. Containment is transitive: if region A contains B and B contains C, then A contains C as well. Every region also counts as containing itself.
The lists together describe one hierarchy with a single outermost region. Given two region names region1 and region2, return the smallest region that contains both of them, meaning the containing region that is nested the deepest.
Examples
Example 1
- Input
regions = [["Earth", "Asia", "Europe"], ["Asia", "India", "Japan"], ["India", "Delhi", "Mumbai"], ["Europe", "France"]], region1 = "Delhi", region2 = "Japan"- Output
"Asia"- Why
- Delhi lies in India, which lies in Asia; Japan lies directly in Asia, and nothing smaller holds both.
Example 2
- Input
regions = [["Earth", "Asia", "Europe"], ["Asia", "India", "Japan"], ["India", "Delhi", "Mumbai"], ["Europe", "France"]], region1 = "Mumbai", region2 = "France"- Output
"Earth"- Why
- The two cities sit on different continents, so only the outermost region covers both.
Example 3
- Input
regions = [["Earth", "Asia", "Europe"], ["Asia", "India", "Japan"], ["India", "Delhi", "Mumbai"], ["Europe", "France"]], region1 = "India", region2 = "Delhi"- Output
"India"- Why
- A region counts as containing itself, and India already holds Delhi.
Constraints
2 <= regions.length <= 10^42 <= regions[i].length <= 201 <= regions[i][j].length <= 20; names are made of English letters and digits and are all different.- Every region except the outermost one appears as a child in exactly one list; the lists form a single tree.
region1andregion2both appear inregions.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (climb by rescanning the lists) | O(h · (T + h)) | O(h) |
| Optimal (parent map and ancestor set) | O(T) | O(T) |
1Brute force (climb by rescanning the lists)
O(h · (T + h))Up to 2h parent lookups each scan all T names in the input, and each of the h membership checks scans the chain of length h.O(h)Only the chain of ancestors of `region1` is stored.Do not build any index. To find the parent of a region, scan every list for a list that has the region as a child. Collect the chain of regions from region1 to the root this way, then climb from region2 and return the first region that is in that chain.
parent(x): look through each list; ifxappears at position 1 or later, return the list's first entry. Return null for the root.- Build the list
chain=region1, its parent, its grandparent, ..., up to the root. - Starting from
cur = region2, returncurifchaincontains it, otherwise movecurtoparent(cur).
class Solution {
private String parent(List<List<String>> regions, String x) {
for (List<String> list : regions)
for (int i = 1; i < list.size(); i++)
if (list.get(i).equals(x)) return list.get(0);
return null;
}
public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
List<String> chain = new ArrayList<>();
for (String cur = region1; cur != null; cur = parent(regions, cur)) chain.add(cur);
for (String cur = region2; cur != null; cur = parent(regions, cur))
if (chain.contains(cur)) return cur;
return null;
}
}class Solution:
def _parent(self, regions: List[List[str]], x: str) -> Optional[str]:
for lst in regions:
for i in range(1, len(lst)):
if lst[i] == x:
return lst[0]
return None
def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
chain = []
cur = region1
while cur is not None:
chain.append(cur)
cur = self._parent(regions, cur)
cur = region2
while cur is not None:
if cur in chain:
return cur
cur = self._parent(regions, cur)
return ""class Solution {
const string* parent(const vector<vector<string>>& regions, const string& x) {
for (auto& list : regions)
for (size_t i = 1; i < list.size(); i++)
if (list[i] == x) return &list[0];
return nullptr;
}
public:
string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
vector<string> chain;
for (const string* cur = ®ion1; cur != nullptr; cur = parent(regions, *cur)) chain.push_back(*cur);
for (const string* cur = ®ion2; cur != nullptr; cur = parent(regions, *cur))
if (find(chain.begin(), chain.end(), *cur) != chain.end()) return *cur;
return "";
}
};function findSmallestRegion(regions, region1, region2) {
const parent = (x) => {
for (const list of regions)
for (let i = 1; i < list.length; i++)
if (list[i] === x) return list[0];
return null;
};
const chain = [];
for (let cur = region1; cur !== null; cur = parent(cur)) chain.push(cur);
for (let cur = region2; cur !== null; cur = parent(cur))
if (chain.includes(cur)) return cur;
return "";
}2Optimal (parent map and ancestor set)
O(T)Building the map touches each of the T names once; both climbs take at most h ≤ T steps with O(1) hash operations (treating names as short).O(T)The parent map has one entry per region, and the set holds at most h of them.One pass over the lists records the direct parent of every child region in a hash map. Walking up from region1 and storing every region seen in a hash set gives all regions that contain region1. Walking up from region2, the first region already in the set is the smallest region holding both.
- For each list, map every entry after the first to the first entry:
parent[child] = list[0]. - Add
region1and each of its ancestors (followparentuntil it is missing) to a set. - Follow
parentfromregion2; return the first region found in the set.
class Solution {
public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
Map<String, String> parent = new HashMap<>();
for (List<String> list : regions)
for (int i = 1; i < list.size(); i++) parent.put(list.get(i), list.get(0));
Set<String> ancestors = new HashSet<>();
for (String cur = region1; cur != null; cur = parent.get(cur)) ancestors.add(cur);
for (String cur = region2; cur != null; cur = parent.get(cur))
if (ancestors.contains(cur)) return cur;
return null;
}
}class Solution:
def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
parent = {}
for lst in regions:
for child in lst[1:]:
parent[child] = lst[0]
ancestors = set()
cur = region1
while cur is not None:
ancestors.add(cur)
cur = parent.get(cur)
cur = region2
while cur is not None:
if cur in ancestors:
return cur
cur = parent.get(cur)
return ""class Solution {
public:
string findSmallestRegion(vector<vector<string>>& regions, string region1, string region2) {
unordered_map<string, string> parent;
for (auto& list : regions)
for (size_t i = 1; i < list.size(); i++) parent[list[i]] = list[0];
unordered_set<string> ancestors;
string cur = region1;
while (true) {
ancestors.insert(cur);
auto it = parent.find(cur);
if (it == parent.end()) break;
cur = it->second;
}
cur = region2;
while (true) {
if (ancestors.count(cur)) return cur;
auto it = parent.find(cur);
if (it == parent.end()) break;
cur = it->second;
}
return "";
}
};function findSmallestRegion(regions, region1, region2) {
const parent = new Map();
for (const list of regions)
for (let i = 1; i < list.length; i++) parent.set(list[i], list[0]);
const ancestors = new Set();
for (let cur = region1; cur !== undefined; cur = parent.get(cur)) ancestors.add(cur);
for (let cur = region2; cur !== undefined; cur = parent.get(cur))
if (ancestors.has(cur)) return cur;
return "";
}Edge cases to test
- One region contains the other, so the answer is one of the inputs
region1 == region2- The only common region is the outermost one
- A very deep chain of nested regions
Hints
Hint 1
Each region has exactly one direct parent, so the lists describe a tree. The question is a lowest common ancestor query.
Hint 2
Record each region's parent in a hash map. Then you can walk from any region up to the root.
Hint 3
Put every region on the path from region1 to the root into a set; the first region on the path from region2 upward that is in the set is the answer.
FAQ
What is the best time complexity for Smallest Common Region?
Optimal (parent map and ancestor set) runs in O(T) time and O(T) extra space. Building the map touches each of the T names once; both climbs take at most h ≤ T steps with O(1) hash operations (treating names as short).
Which pattern does Smallest Common Region use?
It is a trees & bst problem that uses the lca pattern. Other problems with the same pattern: Lowest Common Ancestor of a Binary Tree, Lowest Common Ancestor of a Binary Search Tree, Lowest Common Ancestor of a Binary Tree IV.
Is there a brute force solution for Smallest Common Region?
Yes. Brute force (climb by rescanning the lists) takes O(h · (T + h)) time and O(h) space. Do not build any index.
Which edge cases should I test for Smallest Common Region?
One region contains the other, so the answer is one of the inputs; region1 == region2; The only common region is the outermost one; A very deep chain of nested regions.