Smallest common region

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

68.3% acceptance

Mar 31, 2026

496

No description available.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn find_smallest_region(regions: Vec<Vec<String>>, region1: String, region2: String) -> String {
    let mut parent: HashMap<String, String> = HashMap::new();
    for region in &regions {
      for i in 1..region.len() {
        parent.insert(region[i].clone(), region[0].clone());
      }
    }
    // Find ancestors of region1
    let mut ancestors = std::collections::HashSet::new();
    let mut cur = region1.clone();
    ancestors.insert(cur.clone());
    while let Some(p) = parent.get(&cur) {
      ancestors.insert(p.clone());
      cur = p.clone();
    }
    // Walk up from region2 until we find common ancestor
    let mut cur = region2.clone();
    if ancestors.contains(&cur) { return cur; }
    while let Some(p) = parent.get(&cur) {
      if ancestors.contains(p) { return p.clone(); }
      cur = p.clone();
    }
    cur
  }
}