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

1
2
3
4
5

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

1
2
3

Input: n = 3, paths = [[0],[1],[2]]
Output: 0
Explanation: There is no common subpath shared by the three paths.

Example 3

1
2
3
4

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^5
  • m == paths.length
  • 2 <= m <= 10^5
  • sum(paths[i].length) <= 10^5
  • 0 <= 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

  1. Set left and right bounds for binary search: 0 and the minimum path length.
  2. For each length mid, use rolling hash to get all subpaths of that length for each path.
  3. 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).
  4. If the intersection is non-empty, a common subpath of length mid exists; try a longer length. Otherwise, try a shorter length.
  5. Return the maximum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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.