Skip to main content
Talentd

Smallest Common Region - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableStringTree8 min readAsked at: Airbnb
Practice this problem

Problem Statement

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 <= 104
  • 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.

Approach Overview

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.

Solution

We can use a hash table g to store the parent region of each region. Then, starting from region1, we keep moving upwards to find all its parent regions until the root region, and store these regions in the set s. Next, starting from region2, we keep moving upwards to find the first region that is in the set s, which is the smallest common region.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the region list regions.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Parent Map + Ancestor Set (Hash Table)O(n)O(n)Best general solution; simple and efficient for hierarchy inputs
Explicit Tree + DFS LCAO(n)O(n)Useful when practicing classic tree LCA techniques
Parent Map + Ancestor Path ComparisonO(n)O(n)Works when you prefer comparing ancestor chains instead of hash sets

Video Solution

1257 Smallest Common Region (Biweekly Contest 13) • Kelvin Chandra • 1,484 views views

Watch 3 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Smallest Common Region with our built-in code editor and test cases.

Practice on FleetCode
Previous

Lowest Common Ancestor of a Binary Search Tree

Next

Lowest Common Ancestor of a Binary Tree