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] < npaths[i].The key challenge in Longest Common Subpath is finding the maximum length subpath that appears in every path. A practical strategy is to combine binary search with rolling hash (Rabin–Karp). Instead of checking every possible length, binary search is used on the answer (the length of the common subpath). For each candidate length k, compute rolling hashes for all subpaths of length k in each path and track intersections across paths using hash sets.
If a hash value appears in every path, a common subpath of length k exists, and the search continues for larger values. Otherwise, the search space shrinks. Care must be taken to handle collisions using double hashing or large mod values. Alternative theoretical solutions involve suffix arrays or suffix automata, but the binary search + rolling hash approach is typically more practical for interview settings.
This approach runs in roughly O(N log M) time depending on path lengths, with additional hashing space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search + Rolling Hash | O(N log M) | O(N) |
| Suffix Array Based Approach | O(N log N) | O(N) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
If there is a common path with length x, there is for sure a common path of length y where y < x.
We can use binary search over the answer with the range [0, min(path[i].length)].
Using binary search, we want to verify if we have a common path of length m. We can achieve this using hashing.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Rolling hash allows fast computation of hashes for all subarrays of a fixed length. This makes it efficient to compare subpaths across multiple paths without directly comparing each sequence element.
Hard string and hashing problems like Longest Common Subpath can appear in advanced interview rounds at top tech companies. They test knowledge of binary search on answers, hashing, and efficient substring comparison techniques.
The most practical approach combines binary search with a rolling hash technique. Binary search guesses the subpath length while rolling hashes efficiently check whether a subpath of that length exists in all paths.
Yes, suffix arrays or suffix automata can theoretically solve this problem by analyzing common substrings across sequences. However, these methods are more complex to implement and are less common in coding interviews compared to rolling hash solutions.