Smallest Common Region

Medium Trees & BST LCA Original on LeetCode

Reported atAirbnb

Smallest Common Region is a medium trees & bst problem solved with the lca pattern. The best approach, optimal (parent map and ancestor set), runs in O(T) time and O(T) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (climb by rescanning the lists) up.

Problem

You are given a list of region lists. In each list regions[i], the first name is a region that directly contains every other name in that list. Containment is transitive: if region A contains B and B contains C, then A contains C as well. Every region also counts as containing itself.

The lists together describe one hierarchy with a single outermost region. Given two region names region1 and region2, return the smallest region that contains both of them, meaning the containing region that is nested the deepest.

Examples

Example 1

Input
regions = [["Earth", "Asia", "Europe"], ["Asia", "India", "Japan"], ["India", "Delhi", "Mumbai"], ["Europe", "France"]], region1 = "Delhi", region2 = "Japan"
Output
"Asia"
Why
Delhi lies in India, which lies in Asia; Japan lies directly in Asia, and nothing smaller holds both.

Example 2

Input
regions = [["Earth", "Asia", "Europe"], ["Asia", "India", "Japan"], ["India", "Delhi", "Mumbai"], ["Europe", "France"]], region1 = "Mumbai", region2 = "France"
Output
"Earth"
Why
The two cities sit on different continents, so only the outermost region covers both.

Example 3

Input
regions = [["Earth", "Asia", "Europe"], ["Asia", "India", "Japan"], ["India", "Delhi", "Mumbai"], ["Europe", "France"]], region1 = "India", region2 = "Delhi"
Output
"India"
Why
A region counts as containing itself, and India already holds Delhi.

Constraints

  • 2 <= regions.length <= 10^4
  • 2 <= regions[i].length <= 20
  • 1 <= regions[i][j].length <= 20; names are made of English letters and digits and are all different.
  • Every region except the outermost one appears as a child in exactly one list; the lists form a single tree.
  • region1 and region2 both appear in regions.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (climb by rescanning the lists)O(h · (T + h))O(h)
Optimal (parent map and ancestor set)O(T)O(T)

1Brute force (climb by rescanning the lists)

TimeO(h · (T + h))Up to 2h parent lookups each scan all T names in the input, and each of the h membership checks scans the chain of length h.
SpaceO(h)Only the chain of ancestors of `region1` is stored.

Do not build any index. To find the parent of a region, scan every list for a list that has the region as a child. Collect the chain of regions from region1 to the root this way, then climb from region2 and return the first region that is in that chain.

  1. parent(x): look through each list; if x appears at position 1 or later, return the list's first entry. Return null for the root.
  2. Build the list chain = region1, its parent, its grandparent, ..., up to the root.
  3. Starting from cur = region2, return cur if chain contains it, otherwise move cur to parent(cur).
class Solution {
    private String parent(List<List<String>> regions, String x) {
        for (List<String> list : regions)
            for (int i = 1; i < list.size(); i++)
                if (list.get(i).equals(x)) return list.get(0);
        return null;
    }

    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        List<String> chain = new ArrayList<>();
        for (String cur = region1; cur != null; cur = parent(regions, cur)) chain.add(cur);
        for (String cur = region2; cur != null; cur = parent(regions, cur))
            if (chain.contains(cur)) return cur;
        return null;
    }
}

2Optimal (parent map and ancestor set)

TimeO(T)Building the map touches each of the T names once; both climbs take at most h ≤ T steps with O(1) hash operations (treating names as short).
SpaceO(T)The parent map has one entry per region, and the set holds at most h of them.

One pass over the lists records the direct parent of every child region in a hash map. Walking up from region1 and storing every region seen in a hash set gives all regions that contain region1. Walking up from region2, the first region already in the set is the smallest region holding both.

  1. For each list, map every entry after the first to the first entry: parent[child] = list[0].
  2. Add region1 and each of its ancestors (follow parent until it is missing) to a set.
  3. Follow parent from region2; return the first region found in the set.
class Solution {
    public String findSmallestRegion(List<List<String>> regions, String region1, String region2) {
        Map<String, String> parent = new HashMap<>();
        for (List<String> list : regions)
            for (int i = 1; i < list.size(); i++) parent.put(list.get(i), list.get(0));
        Set<String> ancestors = new HashSet<>();
        for (String cur = region1; cur != null; cur = parent.get(cur)) ancestors.add(cur);
        for (String cur = region2; cur != null; cur = parent.get(cur))
            if (ancestors.contains(cur)) return cur;
        return null;
    }
}

Edge cases to test

  • One region contains the other, so the answer is one of the inputs
  • region1 == region2
  • The only common region is the outermost one
  • A very deep chain of nested regions

Hints

Hint 1

Each region has exactly one direct parent, so the lists describe a tree. The question is a lowest common ancestor query.

Hint 2

Record each region's parent in a hash map. Then you can walk from any region up to the root.

Hint 3

Put every region on the path from region1 to the root into a set; the first region on the path from region2 upward that is in the set is the answer.

FAQ

What is the best time complexity for Smallest Common Region?

Optimal (parent map and ancestor set) runs in O(T) time and O(T) extra space. Building the map touches each of the T names once; both climbs take at most h ≤ T steps with O(1) hash operations (treating names as short).

Which pattern does Smallest Common Region use?

It is a trees & bst problem that uses the lca pattern. Other problems with the same pattern: Lowest Common Ancestor of a Binary Tree, Lowest Common Ancestor of a Binary Search Tree, Lowest Common Ancestor of a Binary Tree IV.

Is there a brute force solution for Smallest Common Region?

Yes. Brute force (climb by rescanning the lists) takes O(h · (T + h)) time and O(h) space. Do not build any index.

Which edge cases should I test for Smallest Common Region?

One region contains the other, so the answer is one of the inputs; region1 == region2; The only common region is the outermost one; A very deep chain of nested regions.