Longest Common Subpath
HardPrompt
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 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.
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 <= 105m == paths.length2 <= m <= 105sum(paths[i].length) <= 1050 <= paths[i][j] < n- The same city is not listed multiple times consecutively in
paths[i].
Approaches
2 approaches with complexity analysis and trade-offs.
This approach is a straightforward, brute-force method. The core idea is to generate all possible candidate subpaths from one of the paths and then verify if each candidate exists in all other paths. To slightly optimize, we can choose the shortest path to generate candidates from, as it has the fewest subpaths. We check for the longest possible subpaths first and decrease the length, so the first common subpath found will be the longest.
Algorithm
- Find the path with the minimum length. Let's call it
shortestPath. - Iterate through all possible subpath lengths
L, fromshortestPath.lengthdown to 1. - For each length
L, generate all subpaths ofshortestPath. - For each generated
subpath: a. Assume it's a common subpath (isCommon = true). b. Iterate through all other paths inpaths. c. Check ifsubpathexists in the current path using a naive linear scan. d. If it doesn't exist, setisCommon = falseand break the inner loop. - If after checking all other paths
isCommonis still true, it means we have found the longest common subpath of lengthL. ReturnL. - If the loops complete, no common subpath was found. Return 0.
Walkthrough
The algorithm begins by identifying the shortest path to minimize the number of subpaths we need to check. Then, it iterates from the maximum possible length (the length of this shortest path) down to 1. In each iteration, it extracts all subpaths of the current length from the shortest path. For each of these subpaths, it performs a search across all the other paths to see if it's a common subpath. This verification is done by a simple linear scan. The first length for which a common subpath is found is the answer.
class Solution { public int longestCommonSubpath(int n, int[][] paths) { if (paths == null || paths.length == 0) { return 0; } // Find the shortest path to optimize a bit int shortestPathIdx = 0; for (int i = 1; i < paths.length; i++) { if (paths[i].length < paths[shortestPathIdx].length) { shortestPathIdx = i; } } int[] shortestPath = paths[shortestPathIdx]; for (int len = shortestPath.length; len >= 1; len--) { // Generate all subpaths of length 'len' from the shortest path for (int i = 0; i <= shortestPath.length - len; i++) { int[] subpath = new int[len]; System.arraycopy(shortestPath, i, subpath, 0, len); boolean isCommon = true; // Check if this subpath exists in all other paths for (int j = 0; j < paths.length; j++) { if (!containsSubpath(paths[j], subpath)) { isCommon = false; break; } } if (isCommon) { return len; // Found the longest } } } return 0; } // Helper to check if a path contains a subpath private boolean containsSubpath(int[] path, int[] subpath) { for (int i = 0; i <= path.length - subpath.length; i++) { boolean match = true; for (int j = 0; j < subpath.length; j++) { if (path[i + j] != subpath[j]) { match = false; break; } } if (match) { return true; } } return false; }}Complexity
Time
O(L_s^2 * L_total * L_s), where `L_s` is the length of the shortest path and `L_total` is the sum of all path lengths. This is a rough estimate, but it's a high-degree polynomial in the path lengths and will result in a 'Time Limit Exceeded' error on the given constraints.
Space
O(L_s), where `L_s` is the length of the shortest path. This space is used to store a single candidate subpath.
Trade-offs
Pros
Simple to conceptualize and implement.
Requires minimal auxiliary data structures.
Cons
Extremely high time complexity, making it infeasible for the given constraints.
Repeatedly scans paths, leading to a lot of redundant computations.
This efficient approach combines binary search on the answer with the Rabin-Karp string searching algorithm. The length of the longest common subpath is found by binary searching in the range of possible lengths. For a given length k, we need an efficient way to check if a common subpath of that length exists across all paths. This check is performed using rolling hashes. We compute the hashes of all subpaths of length k for the first path and then iteratively filter these hashes by checking for their presence in the subsequent paths. If any hashes remain after checking all paths, a common subpath of length k exists.
Algorithm
- The problem has a monotonic property: if a common subpath of length
kexists, a common subpath of lengthk-1also exists. This allows for binary searching on the answer (the length). - Set up a binary search range for the length, from
low = 0tohigh = min_len, wheremin_lenis the length of the shortest path. - In each step of the binary search, check if a common subpath of length
mid = low + (high - low) / 2exists using a helper function,check(mid). - If
check(mid)is true, it means lengthmidis possible. We try for a longer path:ans = mid,low = mid + 1. - If
check(mid)is false,midis too long. We search for a shorter path:high = mid - 1. - The
check(k)function uses the Rabin-Karp algorithm with rolling hashes: a. Generate all rolling hashes for subpaths of lengthkin the first path (ideally the shortest one) and store them in aHashSetcalledcommonHashes. b. For each subsequent path, generate its subpath hashes and find the intersection withcommonHashes. UpdatecommonHasheswith the result. c. IfcommonHashesbecomes empty at any point, returnfalse. d. If the loop completes andcommonHashesis not empty, returntrue.
Walkthrough
The solution binary searches for the longest possible length k. The check(k) function is the core of this approach.
To implement check(k), we use a rolling hash to represent each subpath of length k as a single number. This allows for fast comparisons and storage in a hash set.
- Hashing: We pick a base and a large prime modulus. The hash for a subpath
p[0...k-1]is(p[0]*base^(k-1) + p[1]*base^(k-2) + ... + p[k-1]) % mod. The hash for the next windowp[1...k]can be calculated from the previous hash in O(1) time. - Intersection: We start by calculating all subpath hashes for the shortest path and storing them in a set. Then, for each of the other paths, we calculate their subpath hashes and perform a set intersection with our set of common hashes. If the set becomes empty, we know no common subpath of length
kexists.
This process is repeated within the binary search until the optimal length is found.
import java.util.*; class Solution { // Using one hash function for simplicity, but two are recommended for robustness. // Base should be greater than the max value of a city id (n). private static final long BASE = 100001; private static final long MOD = 1_000_000_007; public int longestCommonSubpath(int n, int[][] paths) { int minLen = Integer.MAX_VALUE; int shortestPathIdx = 0; for (int i = 0; i < paths.length; i++) { if (paths[i].length < minLen) { minLen = paths[i].length; shortestPathIdx = i; } } // Move the shortest path to the front to optimize space for the hash set. int[] temp = paths[0]; paths[0] = paths[shortestPathIdx]; paths[shortestPathIdx] = temp; int low = 0, high = minLen, ans = 0; while (low <= high) { int mid = low + (high - low) / 2; if (mid == 0) { low = mid + 1; continue; } if (check(mid, paths)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } private boolean check(int len, int[][] paths) { Set<Long> commonHashes = calculateHashes(paths[0], len); if (commonHashes.isEmpty()) return false; for (int i = 1; i < paths.length; i++) { Set<Long> currentPathHashes = calculateHashes(paths[i], len); commonHashes.retainAll(currentPathHashes); if (commonHashes.isEmpty()) { return false; } } return true; } private Set<Long> calculateHashes(int[] path, int len) { Set<Long> hashes = new HashSet<>(); if (path.length < len) return hashes; long hash = 0; long power = 1; // To store BASE^(len-1) // Calculate hash of the first window and the highest power of BASE for (int i = 0; i < len; i++) { hash = (hash * BASE + (path[i] + 1)) % MOD; if (i < len - 1) { power = (power * BASE) % MOD; } } hashes.add(hash); // Roll the hash for subsequent windows for (int i = len; i < path.length; i++) { long prevTerm = ((long)(path[i - len] + 1) * power) % MOD; hash = (hash - prevTerm + MOD) % MOD; // Remove leading term hash = (hash * BASE + (path[i] + 1)) % MOD; // Add trailing term hashes.add(hash); } return hashes; }}Complexity
Time
O(L_total * log(L_s)), where `L_total` is the sum of the lengths of all paths and `L_s` is the length of the shortest path. The `check` function takes O(L_total) time, and it's called O(log(L_s)) times by the binary search.
Space
O(L_s), where `L_s` is the length of the shortest path. This space is required to store the hashes of the subpaths of the shortest path.
Trade-offs
Pros
Very efficient, with a time complexity suitable for the given constraints.
The combination of binary search and rolling hash is a powerful and standard technique for solving problems involving finding an optimal-length common substring/subarray.
Cons
More complex to implement than brute force.
Requires careful implementation of the rolling hash to avoid bugs (e.g., handling modular arithmetic correctly).
Hash collisions are possible, though unlikely with good hash functions (using two independent hash functions is a robust way to mitigate this).
Solutions
Solution
class Solution { int N = 100010; long[] h = new long[N]; long[] p = new long[N];private int[][] paths; Map<Long, Integer> cnt = new HashMap<>(); Map<Long, Integer> inner = new HashMap<>();public int longestCommonSubpath(int n, int[][] paths) { int left = 0, right = N; for (int[] path : paths) { right = Math.min(right, path.length); } this.paths = paths; while (left < right) { int mid = (left + right + 1) >> 1; if (check(mid)) { left = mid; } else { right = mid - 1; } } return left; }private boolean check(int mid) { cnt.clear(); inner.clear(); p[0] = 1; for (int j = 0; j < paths.length; ++j) { int n = paths[j].length; for (int i = 1; i <= n; ++i) { p[i] = p[i - 1] * 133331; h[i] = h[i - 1] * 133331 + paths[j][i - 1]; } for (int i = mid; i <= n; ++i) { long val = get(i - mid + 1, i); if (!inner.containsKey(val) || inner.get(val) != j) { inner.put(val, j); cnt.put(val, cnt.getOrDefault(val, 0) + 1); } } } int max = 0; for (int val : cnt.values()) { max = Math.max(max, val); } return max == paths.length; }private long get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }}class Solution: def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int: def check(k: int) -> bool: cnt = Counter() for h in hh: vis = set() for i in range(1, len(h) - k + 1): j = i + k - 1 x = (h[j] - h[i - 1] * p[j - i + 1]) % mod if x not in vis: vis . add(x) cnt[x] += 1 return max(cnt . values()) == m m = len(paths) mx = max(len(path) for path in paths) base = 133331 mod = 2 ** 64 + 1 p = [0] * (mx + 1) p[0] = 1 for i in range(1, len(p)): p[i] = p[i - 1] * base % mod hh = [] for path in paths: k = len(path) h = [0] * (k + 1) for i, x in enumerate(path, 1): h[i] = h[i - 1] * base % mod + x hh . append(h) l, r = 0, min(len(path) for path in paths) while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return lVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.