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.

Smallest Common Region — LeetCode 1257 Python Solution

MediumLeetCode PremiumTreeDepth-First SearchBreadth-First SearchArrayHash TableString

Problem: #1257
Pattern: Tree Traversal
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

Python

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 x

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

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.

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.