Smallest Common Region - Practice Coding Problems

Smallest Common Region - Problem

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

You are given some lists of regions where the first region of each list directly contains all other regions in that list.

If a region x contains a region y directly, and region y contains region z directly, then region x is said to contain region z indirectly.

Note that region x also indirectly contains all regions indirectly contained in y. Naturally, if a region x contains (either directly or indirectly) another region y, then x is bigger than or equal to y in size.

Also, by definition, a region x contains itself.

Given two regions: region1 and region2, return the smallest region that contains both of them.

It is guaranteed the smallest region exists.

Input & Output

Example 1 — Basic Hierarchy

$ 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"

› Output: "North America"

💡 Note: Quebec → Canada → North America → Earth, New York → United States → North America → Earth. First common ancestor is North America.

Example 2 — Same Region

$ Input: regions = [["Earth","North America","South America"],["North America","United States","Canada"]], region1 = "Canada", region2 = "Canada"

› Output: "Canada"

💡 Note: Both regions are the same, so Canada contains itself.

Example 3 — Parent-Child Relationship

$ Input: regions = [["Earth","North America"],["North America","United States"]], region1 = "United States", region2 = "North America"

› Output: "North America"

💡 Note: North America directly contains United States, so North America is the smallest common region.

Constraints

1 ≤ regions.length ≤ 10⁴
1 ≤ regions[i].length ≤ 20
1 ≤ regions[i][j].length ≤ 20
All strings consist of English letters and spaces with at most 20 characters.
All strings are unique.
It is guaranteed a valid answer exists.

Visualization

Tap to expand

Understanding the Visualization

Input

Region hierarchy and two target regions

Process

Build parent map and trace paths to root

Output

First common region in both paths

Key Takeaway

🎯 Key Insight: This is a classic Lowest Common Ancestor problem - build parent relationships and find where two ancestor paths first intersect

Asked in

a Amazon 15 G Google 8 M Microsoft 5

This problem is essentially finding the Lowest Common Ancestor (LCA) in a tree structure. The key insight is to build parent relationships from the region lists, then find where the ancestor paths of both regions first intersect. Best approach uses path comparison after building a parent map. Time: O(n + h), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Direct Path Comparison	O(n + h)	O(n)	Build parent map and find lowest common ancestor efficiently
Brute Force - Find All Ancestors	O(n·h)	O(n + h)	For each region, find all ancestors and compare sets

Optimized - Direct Path Comparison — Algorithm Steps

Build parent map from regions
Traverse paths simultaneously from both regions
Return first common region encountered

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Parent Map

Create parent relationships from region lists

Get Both Paths

Find paths from both regions to root

Find Intersection

First common region in paths is the answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_REGIONS 1000
#define MAX_NAME_LEN 100

char parent[MAX_REGIONS][MAX_NAME_LEN];
char names[MAX_REGIONS][MAX_NAME_LEN];
int name_count = 0;

int find_name_index(const char* name) {
    for (int i = 0; i < name_count; i++) {
        if (strcmp(names[i], name) == 0) return i;
    }
    strcpy(names[name_count], name);
    return name_count++;
}

char* solution(char regions[][10][MAX_NAME_LEN], int region_count, char* region1, char* region2) {
    // Build parent map
    memset(parent, 0, sizeof(parent));
    
    for (int i = 0; i < region_count; i++) {
        for (int j = 1; j < 10 && strlen(regions[i][j]) > 0; j++) {
            int child_idx = find_name_index(regions[i][j]);
            int parent_idx = find_name_index(regions[i][0]);
            strcpy(parent[child_idx], names[parent_idx]);
        }
    }
    
    // Get path to root for region1
    char path1[MAX_REGIONS][MAX_NAME_LEN];
    int path1_len = 0;
    char current[MAX_NAME_LEN];
    strcpy(current, region1);
    
    while (strlen(current) > 0) {
        strcpy(path1[path1_len++], current);
        int idx = find_name_index(current);
        if (strlen(parent[idx]) > 0) {
            strcpy(current, parent[idx]);
        } else {
            current[0] = '\0';
        }
    }
    
    // Check path of region2 against path1
    strcpy(current, region2);
    while (strlen(current) > 0) {
        for (int i = 0; i < path1_len; i++) {
            if (strcmp(current, path1[i]) == 0) {
                static char result[MAX_NAME_LEN];
                strcpy(result, current);
                return result;
            }
        }
        int idx = find_name_index(current);
        if (strlen(parent[idx]) > 0) {
            strcpy(current, parent[idx]);
        } else {
            current[0] = '\0';
        }
    }
    
    return "";
}

int main() {
    // Simplified input parsing
    char region1[MAX_NAME_LEN], region2[MAX_NAME_LEN];
    char regions[10][10][MAX_NAME_LEN] = {
        {"Earth","North America","South America",""},
        {"North America","United States","Canada",""},
        {"United States","New York","Boston",""},
        {"Canada","Ontario","Quebec",""},
        {"South America","Brazil","",""}
    };
    
    scanf("%s", region1);
    scanf("%s", region2);
    
    printf("%s\n", solution(regions, 5, region1, region2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + h)

O(n) to build parent map, O(h) to find common ancestor where h is tree height

✓ Linear Growth

Space Complexity

O(n)

Parent map stores all region relationships, no extra ancestor storage needed

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Direct Path Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler