How hard is LeetCode 1923. Longest Common Subpath?

LeetCode 1923. Longest Common Subpath is rated Hard on LeetCode.

What topics does LeetCode 1923. Longest Common Subpath cover?

LeetCode 1923. Longest Common Subpath is tagged Array, Binary Search, Suffix Array, Hash Function and Rolling Hash on LeetCode.

Longest Common Subpath — LeetCode 1923 Python Solution

HardArrayBinary SearchSuffix ArrayHash FunctionRolling Hash

Problem: #1923
Pattern: Monotonic Stack
Reading time: 6 min
Source: leetcode.com

The 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.

Example

Input: n = 5, paths = [[0,1,2,3,4],
Output: 2
Explanation: The longest common subpath is [2,3].

Python solution

Python

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 l

Complexity

Measure	Complexity
Time	O(log n) or O(n log n)
Space	O(1) auxiliary

Pattern: Monotonic Stack

Answer "what is the next greater element" for every position in one pass. LeetCode 1923. Longest Common Subpath is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.

The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1923. Longest Common Subpath?: LeetCode 1923. Longest Common Subpath is rated Hard on LeetCode.
What topics does LeetCode 1923. Longest Common Subpath cover?: LeetCode 1923. Longest Common Subpath is tagged Array, Binary Search, Suffix Array, Hash Function and Rolling Hash on LeetCode.