Leetcode Problem 1257. Smallest Common Region

1257. Smallest Common Region

Leetcode Solutions

Lowest Common Ancestor Approach

  1. Initialize a map parents to store child-parent relationships.
  2. For each list in regions, map each child (from the second element onwards) to its parent (the first element).
  3. Initialize a set ancestryHistory to store the ancestors of region1.
  4. Add region1 to ancestryHistory and update region1 to its parent until it has no parent.
  5. Check if region2 is in ancestryHistory. If not, update region2 to its parent and repeat until region2 is found in ancestryHistory.
  6. Return region2 as the smallest common region.
UML Thumbnail

Recursive Lowest Common Ancestor Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...