Longest Common Subpath - Practice Coding Problems

Longest Common Subpath - Problem

There is a country of n cities numbered from 0 to n - 1. In this country, there is a road connecting every pair of cities.

There are m friends numbered from 0 to m - 1 who are traveling through the country. Each one of them will take a path consisting of some cities. Each path is represented by an integer array that contains the visited cities in order. The path may contain a city more than once, but the same city will not be listed consecutively.

Given an integer n and a 2D integer array paths where paths[i] is an integer array representing the path of the i-th friend, return the length of the longest common subpath that is shared by every friend's path, or 0 if there is no common subpath at all.

A subpath of a path is a contiguous sequence of cities within that path.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, paths = [[0,1,2,3,4],[2,3,4],[4,0,3,2,1,5]]

› Output: 2

💡 Note: The longest common subpath is [2,3] with length 2. It appears in paths[0] as [2,3], in paths[1] as [2,3], and in paths[2] as [3,2] (which contains [2,3] when read in different direction, but we need exact match). Actually, [4] appears in all three paths: paths[0][4], paths[1][2], and paths[2][0]. But [2,3] appears in paths[0][1:3] and paths[1][0:2]. Let's check [3,2]: appears in paths[2][2:4]. So common subpath [3,2] of length 2 exists.

Example 2 — No Common Subpath

$ Input: n = 3, paths = [[0,1,2],[1,2,0],[2,0,1]]

› Output: 0

💡 Note: No subpath of length > 0 appears in all three paths due to different orderings

Example 3 — Single City Common

$ Input: n = 4, paths = [[0,1,2],[2,3],[1,2,3]]

› Output: 1

💡 Note: City 2 appears in all paths: paths[0][2], paths[1][0], paths[2][1]. So longest common subpath has length 1.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ m ≤ 10³
1 ≤ paths[i].length ≤ 10⁵
0 ≤ paths[i][j] < n
All paths[i] are distinct

Visualization

Tap to expand

Understanding the Visualization

Input Paths

Multiple friends each have a path through cities

Find Common Subpaths

Look for contiguous sequences that appear in all paths

Return Max Length

Output the length of the longest common subpath found

Key Takeaway

🎯 Key Insight: Binary search on length + rolling hash enables efficient subpath matching across all friend paths

Asked in

G Google 15 f Facebook 8 a Amazon 5

The key insight is to use binary search on the answer length combined with rolling hash for efficient subpath comparison. We binary search from 0 to minimum path length, and for each candidate length, use polynomial rolling hash to generate all subpaths and find intersection across all friend paths. Best approach is Binary Search + Rolling Hash with Time: O(L × m × log L), Space: O(L × m).

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search with Rolling Hash	O(L × m × log L)	O(L × m)	Binary search on answer length with rolling hash for efficient subpath comparison
Brute Force	O(L⁴ × m)	O(L³)	Generate all possible subpaths and check if they exist in all friend paths

Binary Search with Rolling Hash — Algorithm Steps

Binary search on the answer length from 0 to minimum path length
For each candidate length, use rolling hash to generate all subpaths
Check if any subpath hash appears in all friend paths

Visualization

Tap to expand

Step-by-Step Walkthrough

Binary Search

Search for maximum length where common subpath exists

Rolling Hash

Generate hash for all subpaths of candidate length

Intersection

Find hash values that appear in all friend paths

Code -

solution.c — C

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

#define MOD 1000000007
#define BASE 100007
#define HASH_SIZE 10007

typedef struct HashNode {
    long long hash;
    struct HashNode* next;
} HashNode;

typedef struct {
    HashNode* buckets[HASH_SIZE];
} HashSet;

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp /= 2;
        base = (base * base) % mod;
    }
    return result;
}

long long modInverse(long long a, long long m) {
    return modPow(a, m - 2, m);
}

void initHashSet(HashSet* set) {
    for (int i = 0; i < HASH_SIZE; i++) {
        set->buckets[i] = NULL;
    }
}

void insertHash(HashSet* set, long long hash) {
    int bucket = hash % HASH_SIZE;
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->hash = hash;
    node->next = set->buckets[bucket];
    set->buckets[bucket] = node;
}

int containsHash(HashSet* set, long long hash) {
    int bucket = hash % HASH_SIZE;
    HashNode* node = set->buckets[bucket];
    while (node) {
        if (node->hash == hash) return 1;
        node = node->next;
    }
    return 0;
}

void freeHashSet(HashSet* set) {
    for (int i = 0; i < HASH_SIZE; i++) {
        HashNode* node = set->buckets[i];
        while (node) {
            HashNode* temp = node;
            node = node->next;
            free(temp);
        }
    }
}

int hasCommonSubpath(int** paths, int* pathSizes, int pathsSize, int length) {
    if (length == 0) return 1;
    
    HashSet firstHashes;
    initHashSet(&firstHashes);
    
    if (pathSizes[0] >= length) {
        long long hashVal = 0;
        long long power = 1;
        
        for (int i = 0; i < length; i++) {
            hashVal = (hashVal + (paths[0][i] * power) % MOD) % MOD;
            if (i < length - 1) {
                power = (power * BASE) % MOD;
            }
        }
        insertHash(&firstHashes, hashVal);
        
        long long basePower = power;
        long long baseInv = modInverse(BASE, MOD);
        
        for (int i = 1; i <= pathSizes[0] - length; i++) {
            hashVal = (hashVal - paths[0][i-1] + MOD) % MOD;
            hashVal = (hashVal * baseInv) % MOD;
            hashVal = (hashVal + (paths[0][i+length-1] * basePower) % MOD) % MOD;
            insertHash(&firstHashes, hashVal);
        }
    }
    
    for (int j = 1; j < pathsSize; j++) {
        if (pathSizes[j] < length) {
            freeHashSet(&firstHashes);
            return 0;
        }
        
        HashSet currentHashes;
        initHashSet(&currentHashes);
        
        long long hashVal = 0;
        long long power = 1;
        
        for (int i = 0; i < length; i++) {
            hashVal = (hashVal + (paths[j][i] * power) % MOD) % MOD;
            if (i < length - 1) {
                power = (power * BASE) % MOD;
            }
        }
        insertHash(&currentHashes, hashVal);
        
        long long basePower = power;
        long long baseInv = modInverse(BASE, MOD);
        
        for (int i = 1; i <= pathSizes[j] - length; i++) {
            hashVal = (hashVal - paths[j][i-1] + MOD) % MOD;
            hashVal = (hashVal * baseInv) % MOD;
            hashVal = (hashVal + (paths[j][i+length-1] * basePower) % MOD) % MOD;
            insertHash(&currentHashes, hashVal);
        }
        
        // Check intersection
        int hasIntersection = 0;
        for (int i = 0; i < HASH_SIZE; i++) {
            HashNode* node = firstHashes.buckets[i];
            while (node) {
                if (containsHash(&currentHashes, node->hash)) {
                    hasIntersection = 1;
                    break;
                }
                node = node->next;
            }
            if (hasIntersection) break;
        }
        
        freeHashSet(&currentHashes);
        if (!hasIntersection) {
            freeHashSet(&firstHashes);
            return 0;
        }
    }
    
    freeHashSet(&firstHashes);
    return 1;
}

int solution(int n, int** paths, int* pathSizes, int pathsSize) {
    if (pathsSize == 0) return 0;
    
    int left = 0, right = pathSizes[0];
    for (int i = 1; i < pathsSize; i++) {
        if (pathSizes[i] < right) {
            right = pathSizes[i];
        }
    }
    
    int result = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (hasCommonSubpath(paths, pathSizes, pathsSize, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    static int paths[100][1000];
    static int pathSizes[100];
    int pathsSize = 0;
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Basic parsing
    char* ptr = line + 1;
    while (*ptr && pathsSize < 100) {
        if (*ptr == '[') {
            ptr++;
            int pathLen = 0;
            while (*ptr && *ptr != ']' && pathLen < 1000) {
                if (*ptr >= '0' && *ptr <= '9') {
                    int num = 0;
                    while (*ptr >= '0' && *ptr <= '9') {
                        num = num * 10 + (*ptr - '0');
                        ptr++;
                    }
                    paths[pathsSize][pathLen++] = num;
                } else {
                    ptr++;
                }
            }
            pathSizes[pathsSize] = pathLen;
            pathsSize++;
        }
        ptr++;
    }
    
    int* pathPtrs[100];
    for (int i = 0; i < pathsSize; i++) {
        pathPtrs[i] = paths[i];
    }
    
    int result = solution(n, pathPtrs, pathSizes, pathsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(L × m × log L)

Binary search log L times, each iteration processes L×m subpaths with rolling hash

⚡ Linearithmic

Space Complexity

O(L × m)

Hash sets to store subpaths for each friend and length

✓ Linear Space

8.2K Views

Medium Frequency

~45 min Avg. Time

267 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

Binary Search with Rolling Hash — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler