Smallest Shared Territory

Medium

A map is split into nested territories. Each row of areas is a list of names: the first name is a territory and the rest are its direct parts. Every territory belongs to at most one larger one, and a single territory contains all the others, directly or through other territories. A territory counts as containing itself. Given two different names first and second, find the smallest territory that contains both and return its name.

Example 1

areas=[["Valley", "North", "South"], ["North", "Mill", "Farm"], ["South", "Port"], ["Farm", "Barn"]], first="Barn", second="Mill" → 'North'

Barn is inside Farm, which is inside North; Mill is inside North too. No smaller territory holds both.

Example 2

areas=[["Valley", "North", "South"], ["North", "Mill", "Farm"], ["South", "Port"], ["Farm", "Barn"]], first="Port", second="Farm" → 'Valley'

They lie in different halves of the valley, so only Valley holds both.

Example 3

areas=[["Island", "Cove", "Peak"], ["Cove", "Pier"]], first="Cove", second="Pier" → 'Cove'

A territory contains itself, so the answer is Cove.

Constraints

1 ≤ len(areas) ≤ 10⁴
2 ≤ len(areas[i]) ≤ 20
1 ≤ length of each name ≤ 20
first ≠ second, both appear on the map
Every territory has at most one enclosing territory; one territory encloses all

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Array Hash Table String

Similar problems

Stop a Process Branch Medium Merge Contact Cards Medium Chains of Synonyms Medium Rearrange Through Links Medium Rooms Open from the Hall Medium

Input

areas=[["Valley", "North", "South"], ["North", "Mill", "Farm"], ["South", "Port"], ["Farm", "Barn"]], first="Barn", second="Mill"

Expected

'North'

Run checks the first 3 tests in your browser. Submit checks all 63 tests on the server, hidden ones included.