Medium

Smallest Common Region

LAB

Regions are encoded as rows [parent, child1, child2, ...]. Return the smallest region containing both query regions.

EXAMPLES

Example 1

Input
{
  "regions": [
    [
      0,
      1,
      2
    ],
    [
      1,
      3,
      4
    ],
    [
      2,
      5,
      6
    ]
  ],
  "names": [
    "Earth",
    "North America",
    "South America",
    "United States",
    "Canada",
    "Brazil",
    "Argentina"
  ],
  "region1": "Canada",
  "region2": "United States"
}

Output
"North America"

FUNCTION SHAPE

regions: intMatrixnames: stringArrayregion1: stringregion2: string→string

SOLUTION NOTE

The key insight is recognizing this is a tree LCA problem! Model the region hierarchy as a tree, build parent pointers, and run LCA.

Reveal reference solution +

pythonREFERENCE

def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
    # Build parent pointers
    parent = defaultdict(str)
    for region in regions:
        for i in range(1, len(region)):
            parent[region[i]] = region[0]

    # Do LCA with parent pointers
    og_p, og_q = region1, region2
    p, q = og_p, og_q
    while p != q:
        p = parent[p] if p else og_q
        q = parent[q] if q else og_p
    return p

TimeO(n)

SpaceO(n)

Open on LeetCode ↗