Longest Common Subpath
HardUpdated: Aug 2, 2025
Practice on:
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 ith friend, return _the length of thelongest 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.
Examples
Example 1
Input: n = 5, paths = [[0,1,_2,3_ ,4],
[_2,3_ ,4],
[4,0,1,_2,3_]]
Output: 2
Explanation: The longest common subpath is [2,3].
Example 2
Input: n = 3, paths = [[0],[1],[2]]
Output: 0
Explanation: There is no common subpath shared by the three paths.
Example 3
Input: n = 5, paths = [[_0_ ,1,2,3,4],
[4,3,2,1,_0_]]
Output: 1
Explanation: The possible longest common subpaths are [0], [1], [2], [3], and [4]. All have a length of 1.
Constraints
1 <= n <= 10^5m == paths.length2 <= m <= 10^5sum(paths[i].length) <= 10^50 <= paths[i][j] < n- The same city is not listed multiple times consecutively in
paths[i].
Solution
Method 1 – Binary Search + Rolling Hash (1)
Intuition
We want the longest subpath (contiguous segment) that appears in every path. We can use binary search on the possible length and check for each length if a common subpath exists using a rolling hash (Rabin-Karp) to efficiently compare subpaths.
Approach
- Set left and right bounds for binary search: 0 and the minimum path length.
- For each length mid, use rolling hash to get all subpaths of that length for each path.
- For the first path, store all hashes in a set. For each subsequent path, keep only hashes that are present in all previous sets (intersection).
- If the intersection is non-empty, a common subpath of length mid exists; try a longer length. Otherwise, try a shorter length.
- Return the maximum length found.
Code
C++
class Solution {
public:
int longestCommonSubpath(int n, vector<vector<int>>& paths) {
int left = 0, right = INT_MAX;
for (auto& p : paths) right = min(right, (int)p.size());
const long long mod = (1LL << 61) - 1, base = 100007;
auto check = [&](int len) -> bool {
unordered_set<long long> s;
for (int i = 0; i < paths.size(); ++i) {
unordered_set<long long> cur;
long long h = 0, pow = 1;
for (int j = 0; j < len; ++j) h = (h * base + paths[i][j]) % mod, pow = (pow * base) % mod;
cur.insert(h);
for (int j = len; j < paths[i].size(); ++j) {
h = (h * base - paths[i][j-len] * pow % mod + mod) % mod;
h = (h + paths[i][j]) % mod;
cur.insert(h);
}
if (i == 0) s = cur;
else {
unordered_set<long long> tmp;
for (auto x : cur) if (s.count(x)) tmp.insert(x);
s = tmp;
}
if (s.empty()) return false;
}
return !s.empty();
};
while (left < right) {
int mid = (left + right + 1) / 2;
if (check(mid)) left = mid;
else right = mid - 1;
}
return left;
}
};
Go
func longestCommonSubpath(n int, paths [][]int) int {
left, right := 0, 1<<31-1
for _, p := range paths {
if len(p) < right {
right = len(p)
}
}
mod, base := int64(1<<61-1), int64(100007)
check := func(len_ int) bool {
var s map[int64]struct{}
for i, path := range paths {
cur := map[int64]struct{}{}
var h, pow int64 = 0, 1
for j := 0; j < len_; j++ {
h = (h*base + int64(path[j])) % mod
pow = (pow * base) % mod
}
cur[h] = struct{}{}
for j := len_; j < len(path); j++ {
h = (h*base - int64(path[j-len_])*pow%mod + mod) % mod
h = (h + int64(path[j])) % mod
cur[h] = struct{}{}
}
if i == 0 {
s = cur
} else {
tmp := map[int64]struct{}{}
for x := range cur {
if _, ok := s[x]; ok {
tmp[x] = struct{}{}
}
}
s = tmp
}
if len(s) == 0 {
return false
}
}
return len(s) > 0
}
for left < right {
mid := (left + right + 1) / 2
if check(mid) {
left = mid
} else {
right = mid - 1
}
}
return left
}
Java
class Solution {
public int longestCommonSubpath(int n, int[][] paths) {
int left = 0, right = Integer.MAX_VALUE;
for (int[] p : paths) right = Math.min(right, p.length);
long mod = (1L << 61) - 1, base = 100007;
java.util.function.IntPredicate check = len -> {
Set<Long> s = new HashSet<>();
for (int i = 0; i < paths.length; i++) {
Set<Long> cur = new HashSet<>();
long h = 0, pow = 1;
for (int j = 0; j < len; j++) {
h = (h * base + paths[i][j]) % mod;
pow = (pow * base) % mod;
}
cur.add(h);
for (int j = len; j < paths[i].length; j++) {
h = (h * base - paths[i][j-len] * pow % mod + mod) % mod;
h = (h + paths[i][j]) % mod;
cur.add(h);
}
if (i == 0) s = cur;
else {
Set<Long> tmp = new HashSet<>();
for (long x : cur) if (s.contains(x)) tmp.add(x);
s = tmp;
}
if (s.isEmpty()) return false;
}
return !s.isEmpty();
};
while (left < right) {
int mid = (left + right + 1) / 2;
if (check.test(mid)) left = mid;
else right = mid - 1;
}
return left;
}
}
Kotlin
class Solution {
fun longestCommonSubpath(n: Int, paths: Array<IntArray>): Int {
var left = 0
var right = paths.minOf { it.size }
val mod = (1L shl 61) - 1
val base = 100007L
fun check(len: Int): Boolean {
var s: Set<Long>? = null
for (i in paths.indices) {
val cur = mutableSetOf<Long>()
var h = 0L
var pow = 1L
for (j in 0 until len) {
h = (h * base + paths[i][j]) % mod
pow = (pow * base) % mod
}
cur.add(h)
for (j in len until paths[i].size) {
h = (h * base - paths[i][j-len] * pow % mod + mod) % mod
h = (h + paths[i][j]) % mod
cur.add(h)
}
s = if (i == 0) cur else s!!.intersect(cur)
if (s.isEmpty()) return false
}
return s!!.isNotEmpty()
}
while (left < right) {
val mid = (left + right + 1) / 2
if (check(mid)) left = mid else right = mid - 1
}
return left
}
}
Python
class Solution:
def longestCommonSubpath(self, n: int, paths: list[list[int]]) -> int:
def check(length: int) -> bool:
mod, base = (1 << 61) - 1, 100007
s = set()
for i, path in enumerate(paths):
cur = set()
h, powb = 0, 1
for j in range(length):
h = (h * base + path[j]) % mod
powb = (powb * base) % mod
cur.add(h)
for j in range(length, len(path)):
h = (h * base - path[j-length] * powb % mod + mod) % mod
h = (h + path[j]) % mod
cur.add(h)
if i == 0:
s = cur
else:
s &= cur
if not s:
return False
return bool(s)
left, right = 0, min(len(p) for p in paths)
while left < right:
mid = (left + right + 1) // 2
if check(mid):
left = mid
else:
right = mid - 1
return left
Rust
impl Solution {
pub fn longest_common_subpath(_n: i32, paths: Vec<Vec<i32>>) -> i32 {
let mut left = 0;
let mut right = paths.iter().map(|p| p.len()).min().unwrap();
let mod_ = (1u64 << 61) - 1;
let base = 100_007u64;
let check = |len: usize| -> bool {
let mut s = std::collections::HashSet::new();
for (i, path) in paths.iter().enumerate() {
let mut cur = std::collections::HashSet::new();
let (mut h, mut pow) = (0u64, 1u64);
for j in 0..len {
h = (h * base + path[j] as u64) % mod_;
pow = (pow * base) % mod_;
}
cur.insert(h);
for j in len..path.len() {
h = (h * base + mod_ - (path[j-len] as u64 * pow % mod_)) % mod_;
h = (h + path[j] as u64) % mod_;
cur.insert(h);
}
if i == 0 {
s = cur;
} else {
s = s.intersection(&cur).cloned().collect();
}
if s.is_empty() { return false; }
}
!s.is_empty()
};
while left < right {
let mid = (left + right + 1) / 2;
if check(mid) {
left = mid;
} else {
right = mid - 1;
}
}
left as i32
}
}
TypeScript
class Solution {
longestCommonSubpath(n: number, paths: number[][]): number {
let left = 0, right = Math.min(...paths.map(p => p.length));
const mod = BigInt(2 ** 61 - 1), base = BigInt(100007);
function check(len: number): boolean {
let s = new Set<bigint>();
for (let i = 0; i < paths.length; i++) {
let cur = new Set<bigint>();
let h = BigInt(0), pow = BigInt(1);
for (let j = 0; j < len; j++) {
h = (h * base + BigInt(paths[i][j])) % mod;
pow = (pow * base) % mod;
}
cur.add(h);
for (let j = len; j < paths[i].length; j++) {
h = (h * base - BigInt(paths[i][j-len]) * pow % mod + mod) % mod;
h = (h + BigInt(paths[i][j])) % mod;
cur.add(h);
}
if (i === 0) s = cur;
else s = new Set([...s].filter(x => cur.has(x)));
if (s.size === 0) return false;
}
return s.size > 0;
}
while (left < right) {
const mid = Math.floor((left + right + 1) / 2);
if (check(mid)) left = mid;
else right = mid - 1;
}
return left;
}
}
Complexity
- ⏰ Time complexity:
O(M * L * log L), where M is the number of paths and L is the minimum path length. Each binary search step checks all subpaths. - 🧺 Space complexity:
O(M * L), for storing hashes of subpaths.