1923. Longest Common Subpath

HardArrayBinary SearchSuffix ArrayHash FunctionRolling Hash

Problem Description

You have a country with n cities numbered from 0 to n - 1. Every pair of cities in this country is connected by a road.

There are m friends (numbered from 0 to m - 1) traveling through the country. Each friend follows a specific path through the cities, represented as an array of city numbers in the order they visit them. A friend can visit the same city multiple times in their journey, but the same city won't appear consecutively in their path.

Given:

An integer n (number of cities)
A 2D array paths where paths[i] represents the travel path of the i-th friend

Your task is to find the length of the longest common subpath that appears in every friend's path. If no common subpath exists among all friends, return 0.

A subpath is defined as a contiguous sequence of cities within a path. For example, if a friend's path is [1, 2, 3, 4], then [2, 3] is a subpath, but [1, 3] is not (since it's not contiguous).

The solution uses binary search combined with rolling hash to efficiently find the longest common subpath. The algorithm:

Binary searches on the possible length of the common subpath (from 0 to the minimum path length)
For each candidate length k, uses rolling hash to check if there exists a subpath of length k that appears in all friends' paths
The rolling hash technique allows checking all subpaths of a given length in linear time by computing hash values incrementally
Returns the maximum length where a common subpath exists among all friends

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing a monotonic property: if a common subpath of length k exists among all friends' paths, then any common subpath of length less than k also exists. This creates a feasibility sequence:

Length k:    0    1    2    3    4    5    6
Feasible:    T    T    T    T    F    F    F
                            ↑
                       first_true_index (maximum feasible)

We want to find the maximum length where a common subpath exists. Using our standard binary search template, we track first_true_index as we search.

For each candidate length k, we define feasible(k) as: does there exist a subpath of length k that appears in all friends' paths?

To check efficiently, we use rolling hash:

Compute hash values for all subpaths of length k in each path
Track unique hashes per friend (avoid double-counting)
Count occurrences across all friends
If any hash appears in all m paths, return true

The rolling hash formula: for subpath [a, b, c], hash = a * base^2 + b * base^1 + c * base^0. Adjacent hashes can be computed in O(1) using prefix hashes.

Learn more about Binary Search patterns.

Solution Implementation

1class Solution:
2    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:
3        num_paths = len(paths)
4        max_len = max(len(path) for path in paths)
5
6        # Hash parameters
7        BASE = 133331
8        MOD = 2**64 + 1
9
10        # Precompute powers of base
11        base_powers = [1] * (max_len + 1)
12        for i in range(1, len(base_powers)):
13            base_powers[i] = base_powers[i - 1] * BASE % MOD
14
15        # Compute prefix hashes for all paths
16        path_hashes = []
17        for path in paths:
18            h = [0] * (len(path) + 1)
19            for i, city in enumerate(path, 1):
20                h[i] = (h[i - 1] * BASE + city) % MOD
21            path_hashes.append(h)
22
23        def feasible(length: int) -> bool:
24            """Check if common subpath of given length exists."""
25            if length == 0:
26                return True
27            hash_count = Counter()
28            for h in path_hashes:
29                seen = set()
30                for i in range(1, len(h) - length + 1):
31                    j = i + length - 1
32                    subhash = (h[j] - h[i - 1] * base_powers[length]) % MOD
33                    if subhash not in seen:
34                        seen.add(subhash)
35                        hash_count[subhash] += 1
36            return max(hash_count.values()) == num_paths
37
38        # Binary search with standard template
39        left, right = 0, min(len(path) for path in paths)
40        first_true_index = 0
41
42        while left <= right:
43            mid = (left + right) // 2
44
45            if feasible(mid):
46                first_true_index = mid
47                left = mid + 1
48            else:
49                right = mid - 1
50
51        return first_true_index
52

1class Solution {
2    private static final long BASE = 133331L;
3    private long[] prefixHash;
4    private long[] basePowers;
5    private int[][] paths;
6    private Map<Long, Integer> hashCount = new HashMap<>();
7    private Map<Long, Integer> lastPathIndex = new HashMap<>();
8
9    public int longestCommonSubpath(int n, int[][] paths) {
10        this.paths = paths;
11
12        int minLen = Integer.MAX_VALUE;
13        int maxLen = 0;
14        for (int[] path : paths) {
15            minLen = Math.min(minLen, path.length);
16            maxLen = Math.max(maxLen, path.length);
17        }
18
19        prefixHash = new long[maxLen + 1];
20        basePowers = new long[maxLen + 1];
21
22        // Binary search with standard template
23        int left = 0;
24        int right = minLen;
25        int firstTrueIndex = 0;
26
27        while (left <= right) {
28            int mid = left + (right - left) / 2;
29
30            if (feasible(mid)) {
31                firstTrueIndex = mid;
32                left = mid + 1;
33            } else {
34                right = mid - 1;
35            }
36        }
37
38        return firstTrueIndex;
39    }
40
41    private boolean feasible(int length) {
42        if (length == 0) return true;
43
44        hashCount.clear();
45        lastPathIndex.clear();
46        basePowers[0] = 1;
47
48        for (int pathIdx = 0; pathIdx < paths.length; pathIdx++) {
49            int[] path = paths[pathIdx];
50
51            for (int i = 1; i <= path.length; i++) {
52                basePowers[i] = basePowers[i - 1] * BASE;
53                prefixHash[i] = prefixHash[i - 1] * BASE + path[i - 1];
54            }
55
56            for (int end = length; end <= path.length; end++) {
57                int start = end - length + 1;
58                long hash = prefixHash[end] - prefixHash[start - 1] * basePowers[length];
59
60                if (!lastPathIndex.containsKey(hash) || lastPathIndex.get(hash) != pathIdx) {
61                    lastPathIndex.put(hash, pathIdx);
62                    hashCount.merge(hash, 1, Integer::sum);
63                }
64            }
65        }
66
67        int maxCount = 0;
68        for (int count : hashCount.values()) {
69            maxCount = Math.max(maxCount, count);
70        }
71        return maxCount == paths.length;
72    }
73}
74

1class Solution {
2private:
3    static constexpr long long BASE = 133331LL;
4    vector<long long> prefixHash;
5    vector<long long> basePowers;
6    vector<vector<int>> paths;
7    unordered_map<long long, int> hashCount;
8    unordered_map<long long, int> lastPathIdx;
9
10public:
11    int longestCommonSubpath(int n, vector<vector<int>>& paths) {
12        this->paths = paths;
13
14        int minLen = INT_MAX, maxLen = 0;
15        for (auto& path : paths) {
16            minLen = min(minLen, (int)path.size());
17            maxLen = max(maxLen, (int)path.size());
18        }
19
20        prefixHash.resize(maxLen + 1);
21        basePowers.resize(maxLen + 1);
22
23        // Binary search with standard template
24        int left = 0, right = minLen;
25        int firstTrueIndex = 0;
26
27        while (left <= right) {
28            int mid = left + (right - left) / 2;
29
30            if (feasible(mid)) {
31                firstTrueIndex = mid;
32                left = mid + 1;
33            } else {
34                right = mid - 1;
35            }
36        }
37
38        return firstTrueIndex;
39    }
40
41private:
42    bool feasible(int length) {
43        if (length == 0) return true;
44
45        hashCount.clear();
46        lastPathIdx.clear();
47        basePowers[0] = 1;
48
49        for (int pathIdx = 0; pathIdx < paths.size(); pathIdx++) {
50            auto& path = paths[pathIdx];
51
52            for (int i = 1; i <= path.size(); i++) {
53                basePowers[i] = basePowers[i - 1] * BASE;
54                prefixHash[i] = prefixHash[i - 1] * BASE + path[i - 1];
55            }
56
57            for (int end = length; end <= path.size(); end++) {
58                int start = end - length + 1;
59                long long hash = prefixHash[end] - prefixHash[start - 1] * basePowers[length];
60
61                if (lastPathIdx.find(hash) == lastPathIdx.end() || lastPathIdx[hash] != pathIdx) {
62                    lastPathIdx[hash] = pathIdx;
63                    hashCount[hash]++;
64                }
65            }
66        }
67
68        int maxCount = 0;
69        for (auto& [h, cnt] : hashCount) {
70            maxCount = max(maxCount, cnt);
71        }
72        return maxCount == (int)paths.size();
73    }
74};
75

1function longestCommonSubpath(n: number, paths: number[][]): number {
2    const BASE = 133331n;
3
4    let minLen = Infinity, maxLen = 0;
5    for (const path of paths) {
6        minLen = Math.min(minLen, path.length);
7        maxLen = Math.max(maxLen, path.length);
8    }
9
10    const basePowers: bigint[] = new Array(maxLen + 1);
11    basePowers[0] = 1n;
12    for (let i = 1; i <= maxLen; i++) {
13        basePowers[i] = basePowers[i - 1] * BASE;
14    }
15
16    // Compute prefix hashes
17    const pathHashes: bigint[][] = [];
18    for (const path of paths) {
19        const h: bigint[] = new Array(path.length + 1);
20        h[0] = 0n;
21        for (let i = 1; i <= path.length; i++) {
22            h[i] = h[i - 1] * BASE + BigInt(path[i - 1]);
23        }
24        pathHashes.push(h);
25    }
26
27    const feasible = (length: number): boolean => {
28        if (length === 0) return true;
29
30        const hashCount = new Map<bigint, number>();
31        const lastIdx = new Map<bigint, number>();
32
33        for (let pathIdx = 0; pathIdx < paths.length; pathIdx++) {
34            const h = pathHashes[pathIdx];
35
36            for (let end = length; end < h.length; end++) {
37                const start = end - length + 1;
38                const hash = h[end] - h[start - 1] * basePowers[length];
39
40                if (!lastIdx.has(hash) || lastIdx.get(hash) !== pathIdx) {
41                    lastIdx.set(hash, pathIdx);
42                    hashCount.set(hash, (hashCount.get(hash) || 0) + 1);
43                }
44            }
45        }
46
47        let maxCount = 0;
48        for (const count of hashCount.values()) {
49            maxCount = Math.max(maxCount, count);
50        }
51        return maxCount === paths.length;
52    };
53
54    // Binary search with standard template
55    let left = 0, right = minLen;
56    let firstTrueIndex = 0;
57
58    while (left <= right) {
59        const mid = Math.floor((left + right) / 2);
60
61        if (feasible(mid)) {
62            firstTrueIndex = mid;
63            left = mid + 1;
64        } else {
65            right = mid - 1;
66        }
67    }
68
69    return firstTrueIndex;
70}
71

Solution Approach

The solution uses binary search with the standard template, combined with rolling hash to check feasibility.

Template Structure:

left, right = 0, min(len(path) for path in paths)
first_true_index = 0  # Default: length 0 always works (empty subpath)

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid  # Record this feasible length
        left = mid + 1          # Try larger lengths
    else:
        right = mid - 1         # Try smaller lengths

return first_true_index

Preprocessing - Hash Arrays:

Compute prefix hashes for rolling hash calculation:

for path in paths:
    prefix_hash = [0] * (len(path) + 1)
    for i, city in enumerate(path, 1):
        prefix_hash[i] = (prefix_hash[i-1] * BASE + city) % MOD

This allows O(1) subpath hash: hash(i, j) = (h[j] - h[i-1] * base^(j-i+1)) % mod

Feasibility Check:

For length k, check if any subpath appears in all paths:

For each path, compute hashes of all subpaths of length k
Track unique hashes per path (avoid double-counting)
Count occurrences across all paths
If any hash appears in all m paths, return true

Time Complexity: O(S × log(min_len)) where S = total path length.

Space Complexity: O(S) for prefix hash arrays.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through with paths = [[0,1,2,3,4], [2,3,4], [4,0,1,2,3]].

Step 1: Initialize

left = 0, right = 3 (min path length)
first_true_index = 0

Step 2: Binary search iterations

Iteration 1: left = 0, right = 3

mid = (0 + 3) // 2 = 1
Check for common subpath of length 1:
- All paths contain cities, so any shared city works
- Hash counts: city 2 appears in all 3 paths ✓
Update: first_true_index = 1, left = 1 + 1 = 2

Iteration 2: left = 2, right = 3

mid = (2 + 3) // 2 = 2
Check for common subpath of length 2:
- Path 0: hashes for [0,1], [1,2], [2,3], [3,4]
- Path 1: hashes for [2,3], [3,4]
- Path 2: hashes for [4,0], [0,1], [1,2], [2,3]
- Hash for [2,3] appears in all 3 paths ✓
Update: first_true_index = 2, left = 2 + 1 = 3

Iteration 3: left = 3, right = 3

mid = (3 + 3) // 2 = 3
Check for common subpath of length 3:
- Path 0: [0,1,2], [1,2,3], [2,3,4]
- Path 1: [2,3,4] only
- Path 2: [4,0,1], [0,1,2], [1,2,3]
- No hash appears in all 3 paths ✗
Update: right = 3 - 1 = 2

Step 3: Loop terminates

left = 3 > right = 2
Return first_true_index = 2

The longest common subpath has length 2 (subpath [2,3]).

Time and Space Complexity

Time Complexity: O(S * log(min_len)) where S is the total sum of all path lengths and min_len is the length of the shortest path.

The analysis breaks down as follows:

Binary search runs for O(log(min_len)) iterations
For each binary search iteration, we call the check(k) function
Inside check(k):
- We iterate through all m paths
- For each path of length len(path), we compute rolling hashes for all subpaths of length k, which takes O(len(path) - k + 1) iterations
- Each hash computation is O(1) due to the precomputed prefix hashes
- Total work in check(k) is O(sum(len(path) - k + 1)) for all paths, which is O(S)
Preprocessing step computes prefix hashes for all paths in O(S) time
Overall: O(S) + O(S * log(min_len)) = O(S * log(min_len))

Space Complexity: O(S + mx) where S is the total sum of all path lengths and mx is the length of the longest path.

The space breakdown:

Array p stores powers of base up to mx + 1: O(mx)
Array hh stores prefix hashes for all paths: O(S) total space
Inside check(k):
- cnt Counter can store at most O(S) unique hash values
- vis set for each path stores at most O(len(path)) hashes
Overall: O(S + mx)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using the Wrong Binary Search Template

The Pitfall: Using while left < right with left = mid instead of the standard while left <= right template.

Solution: Use the standard template:

left, right = 0, min(len(path) for path in paths)
first_true_index = 0

while left <= right:
    mid = (left + right) // 2
    if feasible(mid):
        first_true_index = mid
        left = mid + 1
    else:
        right = mid - 1

return first_true_index

2. Hash Collision Issues

The Pitfall: Using a small modulo or base value leads to collisions where different subpaths produce the same hash.

Solution: Use a large prime base (e.g., 133331) and large modulo (e.g., 2^64 + 1). For extra safety, consider double hashing.

3. Duplicate Counting Within a Path

The Pitfall: Counting the same subpath multiple times within one path.

Solution: Use a seen set per path to ensure each unique subpath hash is counted only once:

seen = set()
for start in range(1, len(h) - length + 1):
    subhash = compute_hash(...)
    if subhash not in seen:
        seen.add(subhash)
        hash_count[subhash] += 1

4. Off-by-One Errors in Index Calculations

The Pitfall: Confusion between 0-based and 1-based indexing for prefix hashes.

Solution: Be consistent. Use 1-based indexing where h[i] = hash of path[0:i].

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don't know