LeetCode 1257 - Smallest Common Region

This problem describes a hierarchical relationship between geographic regions. Each list in regions represents a parent-child relationship where the first element is the parent region and every remaining element in the list is directly contained within that parent.

leetcodemediumarrayhash-tablestringtreedepth-first-searchbreadth-first-search

LeetCode Problem 1257

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Tree, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

This problem describes a hierarchical relationship between geographic regions. Each list in regions represents a parent-child relationship where the first element is the parent region and every remaining element in the list is directly contained within that parent.

For example, the list:

["North America", "United States", "Canada"]

means that "North America" directly contains "United States" and "Canada".

The hierarchy forms a tree structure. Every region except the root has exactly one parent because the problem guarantees that a region cannot be directly contained in more than one region. There is also guaranteed to be a single top-level region that indirectly contains all others.

The goal is to find the smallest region that contains both region1 and region2. In tree terminology, this is the Lowest Common Ancestor, often abbreviated as LCA.

For example:

  • "Quebec" belongs to "Canada"
  • "Canada" belongs to "North America"
  • "New York" belongs to "United States"
  • "United States" belongs to "North America"

The smallest region containing both "Quebec" and "New York" is therefore "North America".

The constraints tell us several important things:

  • regions.length <= 10^4, which means we need an efficient solution
  • Each region name is short, so string operations are inexpensive
  • Every node has at most one parent, which strongly suggests a tree structure
  • The answer is guaranteed to exist, so we never need to handle disconnected graphs

Important edge cases include situations where:

  • One region is an ancestor of the other
  • The common ancestor is the root region
  • The tree is very deep
  • The regions belong to completely different branches

A naive implementation that repeatedly searches the hierarchy could become inefficient for deep trees, so we need a method that quickly traces ancestry relationships.

Approaches

Brute Force Approach

A brute force solution would repeatedly search through the entire regions list to determine parent relationships.

For each step upward from region1, we could scan all lists looking for the region that contains it. Then we could do the same for region2. After generating both ancestry chains, we could compare them to find the first common region.

This approach works because eventually both paths reach the root, and the first shared ancestor is the smallest common region.

However, the problem is efficiency. Every time we want to find a parent, we may need to scan the entire input. Since the hierarchy can contain up to 10^4 regions, repeated scanning becomes unnecessarily expensive.

Optimal Approach

The key observation is that the hierarchy forms a tree where every node has exactly one parent.

Instead of repeatedly searching for parents, we can preprocess the input into a hash map:

child -> parent

Once we have direct parent lookup, we can efficiently walk upward through the tree.

The algorithm becomes:

  1. Build a parent map
  2. Walk upward from region1 and store all ancestors in a set
  3. Walk upward from region2
  4. The first ancestor of region2 that appears in the set is the answer

This works because ancestor traversal naturally moves from smaller regions toward larger regions. The first shared ancestor encountered must therefore be the smallest common region.

Approach Time Complexity Space Complexity Notes
Brute Force O(N²) O(N) Repeatedly scans the region lists to locate parents
Optimal O(N) O(N) Uses a parent hash map for direct ancestor traversal

Algorithm Walkthrough

  1. Create a hash map called parent.

This map stores the direct parent of every child region. For every list in regions, the first element is the parent and the remaining elements are children.

Example:

["North America", "United States", "Canada"]

produces:

"United States" -> "North America"
"Canada" -> "North America"

Using a hash map allows constant time parent lookup. 2. Traverse upward from region1.

Start from region1 and repeatedly move to its parent using the map.

Store every visited region in a set called ancestors.

This set represents the entire ancestry chain of region1, including itself. 3. Traverse upward from region2.

Start from region2 and repeatedly move upward.

At each step, check whether the current region exists in the ancestors set.

The first match is the smallest common region because we are moving upward from the deepest possible node. 4. Return the matching region.

Since the problem guarantees a valid answer exists, the traversal will always find a common ancestor.

Why it works

The tree property guarantees that every node has exactly one path to the root. By storing all ancestors of region1, we create a complete record of every region that contains it. Then, when traversing upward from region2, the first ancestor that appears in the set must be the lowest shared ancestor because traversal proceeds from smaller regions toward larger regions.

Python Solution

from typing import List

class Solution:
    def findSmallestRegion(
        self,
        regions: List[List[str]],
        region1: str,
        region2: str
    ) -> str:

        parent = {}

        # Build child -> parent mapping
        for region_list in regions:
            parent_region = region_list[0]

            for i in range(1, len(region_list)):
                child_region = region_list[i]
                parent[child_region] = parent_region

        # Store all ancestors of region1
        ancestors = set()

        current = region1

        while current:
            ancestors.add(current)
            current = parent.get(current)

        # Find first common ancestor while traversing region2
        current = region2

        while current not in ancestors:
            current = parent.get(current)

        return current

The implementation begins by constructing the parent dictionary. Each child region points directly to its containing region, which allows upward traversal through the hierarchy in constant time per step.

Next, the code walks upward from region1. Every visited region is inserted into the ancestors set. This includes region1 itself, its parent, grandparent, and eventually the root region.

The second traversal starts from region2. At every step, the algorithm checks whether the current region already exists in the ancestor set. The first match is immediately returned because it represents the lowest common ancestor.

Using parent.get(current) avoids errors when reaching the root, since the root has no parent entry.

Go Solution

func findSmallestRegion(regions [][]string, region1 string, region2 string) string {
	parent := make(map[string]string)

	// Build child -> parent mapping
	for _, regionList := range regions {
		parentRegion := regionList[0]

		for i := 1; i < len(regionList); i++ {
			childRegion := regionList[i]
			parent[childRegion] = parentRegion
		}
	}

	// Store all ancestors of region1
	ancestors := make(map[string]bool)

	current := region1

	for current != "" {
		ancestors[current] = true
		current = parent[current]
	}

	// Find first common ancestor
	current = region2

	for !ancestors[current] {
		current = parent[current]
	}

	return current
}

The Go solution follows the same logic as the Python version, but there are a few language-specific details worth noting.

Go maps return the zero value when a key does not exist. For strings, the zero value is an empty string "". This behavior naturally terminates traversal when the root region has no parent.

The ancestor set is implemented using map[string]bool because Go does not have a built-in set type.

Unlike Python, Go requires explicit variable declarations and uses slices for the nested region lists.

Worked Examples

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"

Step 1: Build Parent Map

Child Parent
North America Earth
South America Earth
United States North America
Canada North America
New York United States
Boston United States
Ontario Canada
Quebec Canada
Brazil South America

Step 2: Traverse Ancestors of Quebec

Current Region Ancestors Set
Quebec {Quebec}
Canada {Quebec, Canada}
North America {Quebec, Canada, North America}
Earth {Quebec, Canada, North America, Earth}

Step 3: Traverse Upward from New York

Current Region In Ancestors Set?
New York No
United States No
North America Yes

The answer is:

"North America"

Example 2

Input:

region1 = "Canada"
region2 = "South America"

Step 1: Ancestors of Canada

Current Region Ancestors Set
Canada {Canada}
North America {Canada, North America}
Earth {Canada, North America, Earth}

Step 2: Traverse Upward from South America

Current Region In Ancestors Set?
South America No
Earth Yes

The answer is:

"Earth"

Complexity Analysis

Measure Complexity Explanation
Time O(N) Each region is processed at most once while building the map and traversing ancestors
Space O(N) The parent map and ancestor set can together store all regions

The preprocessing step builds a parent mapping for every child region exactly once. The ancestor traversals each move upward through the tree without revisiting nodes. Since the total number of regions is bounded by N, the overall runtime is linear.

The auxiliary space comes from the hash map storing parent relationships and the set storing ancestors of region1.

Test Cases

from typing import List

class Solution:
    def findSmallestRegion(
        self,
        regions: List[List[str]],
        region1: str,
        region2: str
    ) -> str:

        parent = {}

        for region_list in regions:
            parent_region = region_list[0]

            for i in range(1, len(region_list)):
                parent[region_list[i]] = parent_region

        ancestors = set()

        current = region1

        while current:
            ancestors.add(current)
            current = parent.get(current)

        current = region2

        while current not in ancestors:
            current = parent.get(current)

        return current

sol = Solution()

# Example 1
assert sol.findSmallestRegion(
    [
        ["Earth", "North America", "South America"],
        ["North America", "United States", "Canada"],
        ["United States", "New York", "Boston"],
        ["Canada", "Ontario", "Quebec"],
        ["South America", "Brazil"]
    ],
    "Quebec",
    "New York"
) == "North America"  # common ancestor in middle of tree

# Example 2
assert sol.findSmallestRegion(
    [
        ["Earth", "North America", "South America"],
        ["North America", "United States", "Canada"],
        ["United States", "New York", "Boston"],
        ["Canada", "Ontario", "Quebec"],
        ["South America", "Brazil"]
    ],
    "Canada",
    "South America"
) == "Earth"  # common ancestor is root

# One region is ancestor of the other
assert sol.findSmallestRegion(
    [
        ["Earth", "Asia"],
        ["Asia", "China"],
        ["China", "Beijing"]
    ],
    "China",
    "Beijing"
) == "China"  # ancestor should return itself

# Smallest possible hierarchy
assert sol.findSmallestRegion(
    [
        ["Earth", "Asia"]
    ],
    "Earth",
    "Asia"
) == "Earth"  # root and child only

# Deep chain hierarchy
assert sol.findSmallestRegion(
    [
        ["A", "B"],
        ["B", "C"],
        ["C", "D"],
        ["D", "E"]
    ],
    "E",
    "C"
) == "C"  # deep ancestor chain

# Sibling regions
assert sol.findSmallestRegion(
    [
        ["World", "Europe", "Asia"],
        ["Europe", "France", "Germany"]
    ],
    "France",
    "Germany"
) == "Europe"  # direct sibling relationship
Test Why
Quebec and New York Validates standard LCA behavior
Canada and South America Validates root as answer
China and Beijing Tests ancestor-descendant relationship
Earth and Asia Tests minimal valid hierarchy
Deep chain hierarchy Ensures traversal works in deep trees
France and Germany Tests sibling relationship

Edge Cases

One important edge case occurs when one region is already an ancestor of the other. For example, if region1 = "China" and region2 = "Beijing", then "China" itself is the smallest common region. Some incorrect implementations continue traversing upward unnecessarily and return a larger ancestor. This implementation avoids that bug because all ancestors of region1, including itself, are inserted into the set before traversing from region2.

Another important case is when the only shared ancestor is the root region. This happens when the two regions belong to completely separate branches of the hierarchy. A flawed implementation might terminate early or fail to continue traversal all the way to the root. Since this algorithm continues upward until a match is found, it correctly handles cases where the answer is the global root.

A third edge case involves extremely deep hierarchies. Recursive DFS solutions can risk stack overflow if the tree becomes very deep. This implementation uses iterative parent traversal instead of recursion, making it safe and efficient even for long chains of regions.

A subtle case involves regions with no explicit parent entry. The root node never appears as a child, so it is absent from the parent map. Using parent.get(current) in Python and relying on Go's zero-value behavior ensures traversal stops cleanly at the root without raising errors.