Show problems as
Classic problem #1257MediumArrayHash TableStringTreeDepth-First SearchBreadth-First SearchBinary LiftingLowest Common Ancestor

Smallest Common Region

Real-world version: Innermost Zone Holding Both Sites
Tracked in this browser only
Read Smallest Common Region on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A survey is organised into zones. Each entry of regions names a zone first and then the zones lying directly inside it. A zone lies inside another when it is named directly inside it, or inside something that does.

No zone lies directly inside more than one zone, and one zone holds all the others.

Given two distinct zone names region1 and region2, return the name of the innermost zone that holds both of them. A zone counts as holding itself.

Examples

Example 1

Input
regions = [["World", "North", "South"], ["North", "Alba", "Cymru"], ["South", "Kernow"]], region1 = "Alba", region2 = "Cymru"
Output
"North"

Both sites lie directly inside "North", so that is the innermost zone holding them both.

Example 2

Input
regions = [["World", "North", "South"], ["North", "Alba", "Cymru"], ["South", "Kernow"]], region1 = "Alba", region2 = "Kernow"
Output
"World"

One site lies inside "North" and the other inside "South", and the innermost zone holding both of those is "World".

Example 3

Input
regions = [["World", "North", "South"], ["North", "Alba", "Cymru"], ["South", "Kernow"]], region1 = "Alba", region2 = "North"
Output
"North"

A zone counts as holding itself, and "Alba" lies inside "North", so "North" holds them both.

Constraints

  • 2 <= regions.length <= 10^4
  • 2 <= regions[i].length <= 20
  • 1 <= regions[i][j].length <= 20
  • 1 <= region1.length <= 20
  • 1 <= region2.length <= 20
  • region1 and region2 are different names
  • Every name consists of English letters only
  • No zone lies directly inside more than one zone, and one zone holds all the others

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def innermost_holder(regions: list[list[str]], region1: str, region2: str) -> str:
Java
public String innermostHolder(List<List<String>> regions, String region1, String region2)

More on the same topics