MediumNo. 1257LeetCode Premium
Smallest Common Region — LeetCode 1257 Python Solution
- Pattern
- Tree Traversal
- Topics
- Tree, Depth-First Search, Breadth-First Search, Array, Hash Table, String
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- regions = [["Earth","North America","South America"],
- Output
- "North America"
Python solution
class Solution:
def findSmallestRegion(
self, regions: List[List[str]], region1: str, region2: str
) -> str:
g = {}
for r in regions:
x = r[0]
for y in r[1:]:
g[y] = x
s = set()
x = region1
while x in g:
s.add(x)
x = g[x]
x = region2
while x in g and x not in s:
x = g[x]
return xComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1257. Smallest Common Region is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0690 | Employee Importance | Medium |
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 1202 | Smallest String With Swaps | Medium |
| 1993 | Operations on Tree | Medium |
| 2368 | Reachable Nodes With Restrictions | Medium |
Frequently asked questions
- How hard is LeetCode 1257. Smallest Common Region?
LeetCode 1257. Smallest Common Region is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1257. Smallest Common Region?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1257. Smallest Common Region?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1257. Smallest Common Region cover?
LeetCode 1257. Smallest Common Region is tagged Tree, Depth-First Search, Breadth-First Search, Array, Hash Table and String on LeetCode.
- Is LeetCode 1257. Smallest Common Region a premium problem?
Yes. LeetCode 1257. Smallest Common Region is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.