Is Smallest Common Region easy or hard?

Smallest Common Region is rated Medium on LeetCode. The challenge comes from recognizing that the region lists implicitly form a tree and that the task reduces to finding a lowest common ancestor. Once that insight is clear, the hash map solution is straightforward.

Smallest Common Region Python/Java solution

Both Python and Java implementations follow the same steps: build a child-to-parent map, store ancestors of region1 in a set, and move upward from region2 until an ancestor match is found. The algorithm remains O(n) time and O(n) space regardless of language.

How to solve Smallest Common Region in O(n)?

First iterate through the region lists and map every child to its parent using a hash table. Walk from region1 to the root while storing each ancestor in a set. Then repeatedly move from region2 to its parent until a region appears in the set. The first match is the smallest common region.

What is the best approach for Smallest Common Region?

The most efficient approach builds a parent map using a hash table. Each child region is mapped to its parent, allowing upward traversal of the hierarchy. Store all ancestors of region1 in a set, then climb from region2 until a match appears. This finds the smallest common region in O(n) time with O(n) space.

Is Smallest Common Region asked at Google/Amazon/Meta?

Tree hierarchy and Lowest Common Ancestor style problems frequently appear in interviews at companies like Google, Amazon, and Meta. Smallest Common Region tests similar skills: building parent relationships, working with hash maps, and reasoning about tree ancestry.

What data structure is used in Smallest Common Region?

The core data structure is a hash table that maps each region to its parent. A hash set is also used to store ancestors of one region for constant‑time lookup. Conceptually the regions form a tree, so many solutions treat the problem as a Lowest Common Ancestor search.

What is the time complexity of Smallest Common Region?

The optimal solution runs in O(n) time where n is the total number of regions listed in the hierarchy. Building the parent map takes linear time, and traversing the ancestor chains for the two regions also takes at most O(n). Space complexity is O(n) due to the hash table and ancestor set.

1257. Smallest Common Region - Practice Online

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 <= 10⁴
2 <= regions[i].length <= 20
1 <= regions[i][j].length, region1.length, region2.length <= 20
region1 != region2
regions[i][j], region1, and region2 consist of English letters.
The input is generated such that there exists a region which contains all the other regions, either directly or indirectly.
A region cannot be directly contained in more than one region.