In this guide, you will get 1923. Longest Common Subpath LeetCode Solution with the best time and space complexity. The solution to Longest Common Subpath problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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].
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 <= 105
m == paths.length
2 <= m <= 105
sum(paths[i].length) <= 105
0 <= paths[i][j] < n
The same city is not listed multiple times consecutively in paths[i].
Complexity Analysis
Time Complexity: O(mn \log n)
Space Complexity: O(mn)
1923. Longest Common Subpath LeetCode Solution in C++
class Solution {
public:
int longestCommonSubpath(int n, vector<vector<int>>& paths) {
int l = 0;
int r = paths[0].size();
while (l < r) {
const int m = l + (r - l + 1) / 2;
if (checkCommonSubpath(paths, m))
l = m;
else
r = m - 1;
}
return l;
}
static constexpr long kBase = 165'131;
static constexpr long kHash = 8'417'508'174'513;
// Returns true if there's a common subpath of length m for all the paths.
bool checkCommonSubpath(const vector<vector<int>>& paths, int m) {
vector<unordered_set<long>> hashSets;
// Calculate the hash values for subpaths of length m for every path.
for (const vector<int>& path : paths)
hashSets.push_back(rabinKarp(path, m));
// Check if there is a common subpath of length m.
for (const long subpathHash : hashSets[0])
if (ranges::all_of(hashSets,
[subpathHash](const unordered_set<long>& hashSet) {
return hashSet.contains(subpathHash);
}))
return true;
return false;
}
// Returns the hash values for subpaths of length m in the path.
unordered_set<long> rabinKarp(const vector<int>& path, int m) {
unordered_set<long> hashes;
long maxPower = 1;
long hash = 0;
for (int i = 0; i < path.size(); ++i) {
hash = (hash * kBase + path[i]) % kHash;
if (i >= m)
hash = (hash - path[i - m] * maxPower % kHash + kHash) % kHash;
else
maxPower = maxPower * kBase % kHash;
if (i >= m - 1)
hashes.insert(hash);
}
return hashes;
}
}; /* code provided by PROGIEZ */
1923. Longest Common Subpath LeetCode Solution in Java
class Solution {
public int longestCommonSubpath(int n, int[][] paths) {
int l = 0;
int r = paths[0].length;
while (l < r) {
final int m = l + (r - l + 1) / 2;
if (checkCommonSubpath(paths, m))
l = m;
else
r = m - 1;
}
return l;
}
private static final long kBase = 165_131L;
private static final long kHash = 8_417_508_174_513L;
// Returns true if there's a common subpath of length m for all the paths.
private boolean checkCommonSubpath(int[][] paths, int m) {
Set<Long>[] hashSets = new Set[paths.length];
// Calculate the hash values for subpaths of length m for every path.
for (int i = 0; i < paths.length; ++i)
hashSets[i] = rabinKarp(paths[i], m);
// Check if there is a common subpath of length m.
for (final long subpathHash : hashSets[0])
if (Arrays.stream(hashSets).allMatch(hashSet -> hashSet.contains(subpathHash)))
return true;
return false;
}
// Returns the hash values for subpaths of length m in the path.
private Set<Long> rabinKarp(int[] path, int m) {
Set<Long> hashes = new HashSet<>();
long maxPower = 1;
long hash = 0;
for (int i = 0; i < path.length; ++i) {
hash = (hash * kBase + path[i]) % kHash;
if (i >= m)
hash = (hash - path[i - m] * maxPower % kHash + kHash) % kHash;
else
maxPower = maxPower * kBase % kHash;
if (i >= m - 1)
hashes.add(hash);
}
return hashes;
}
} // code provided by PROGIEZ
1923. Longest Common Subpath LeetCode Solution in Python
class Solution:
def __init__(self):
self.kBase = 165_131
self.kHash = 8_417_508_174_513
def longestCommonSubpath(self, n: int, paths: list[list[int]]) -> int:
l = 0
r = len(paths[0])
while l < r:
m = l + (r - l + 1) // 2
if self._checkCommonSubpath(paths, m):
l = m
else:
r = m - 1
return l
def _checkCommonSubpath(self, paths: list[list[int]], m: int) -> bool:
"""
Returns True if there's a common subpath of length m for all the paths.
"""
# Calculate the hash values for subpaths of length m for every path.
hashSets = [self._rabinKarp(path, m) for path in paths]
# Check if there is a common subpath of length m.
for subpathHash in hashSets[0]:
if all(subpathHash in hashSet for hashSet in hashSets):
return True
return False
def _rabinKarp(self, path: list[int], m: int) -> set[int]:
"""Returns the hash values for subpaths of length m in the path."""
hashes = set()
maxPower = 1
hash = 0
for i, num in enumerate(path):
hash = (hash * self.kBase + num) % self.kHash
if i >= m:
hash = (hash - path[i - m] * maxPower %
self.kHash + self.kHash) % self.kHash
else:
maxPower = maxPower * self.kBase % self.kHash
if i >= m - 1:
hashes.add(hash)
return hashes # code by PROGIEZ
