Longest Common Subpath

Hard

Asked by:

14 views

Topics:

ArraysBinary SearchStringsSliding Windows

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 i^th 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 <= 10⁵
m == paths.length
2 <= m <= 10⁵
sum(paths[i].length) <= 10⁵
0 <= paths[i][j] < n
The same city is not listed multiple times consecutively in paths[i].

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the lengths of paths and the number of paths, specifically the maximum values?
Can the same city appear multiple times within a single path, and across different paths?
What should I return if there is no common subpath between all paths, specifically an empty list or a subpath of length zero?
Are the city IDs (integers) guaranteed to be non-negative, and is there a maximum possible city ID value?
If there are multiple longest common subpaths of the same length, is it sufficient to return any one of them?

Brute Force Solution

Approach

The brute force strategy for finding the longest common subpath involves checking every possible subpath length and seeing if that subpath exists in all given paths. We essentially guess a subpath length and then see if we're correct. If not, we try again with a different guess.

Here's how the algorithm would work step-by-step:

Start by guessing the longest possible length for the common subpath. This would be the length of the shortest path.
Now, consider every possible sequence of that length in the first path.
For each sequence from the first path, check if that exact sequence also appears in the second path.
If the sequence appears in the second path, check if it appears in all other paths as well.
If the sequence appears in all paths, you've found a common subpath of the guessed length! You are done.
If no sequence of the guessed length appears in all paths, reduce your guess for the longest possible length by one.
Repeat steps 2-6 with this smaller length.
Keep repeating until you find a length where a common subpath exists in all paths, or until you've tried all possible lengths down to one.

Code Implementation

def longest_common_subpath_brute_force(paths):
    shortest_path_length = min(len(path) for path in paths)

    # Iterate from longest possible length to shortest
    for subpath_length in range(shortest_path_length, 0, -1):
        for i in range(len(paths[0]) - subpath_length + 1):
            subpath = paths[0][i:i + subpath_length]
            
            all_paths_contain = True

            # Check if the subpath exists in all paths
            for path in paths:
                if subpath not in path:
                    all_paths_contain = False
                    break

            # If it exists in all paths, return the length
            if all_paths_contain:
                return subpath_length

    # If no common subpath is found, return 0
    return 0

Big(O) Analysis

Time Complexity

O(m * n * k) – Let n be the number of paths, m be the length of the shortest path (maximum possible length of a common subpath), and k be the average length of all paths. The algorithm iterates downwards from length m to 1, guessing the length of the longest common subpath. For each guess, it extracts all possible subpaths of that length from the first path (m - length + 1). For each subpath, it searches for the existence of that subpath in all other n-1 paths. The search operation in each path can take up to O(k) time. Therefore, the overall complexity is roughly O(m * (m * n * k)).

Space Complexity

O(N) – The described brute force solution's space complexity primarily depends on storing the subpaths being checked. In step 2, for each potential subpath of length L (where L can range from the shortest path's length down to 1), a subpath sequence is created. In the worst-case scenario, the number of such sequences can be proportional to the length of the longest path, which we can denote as N. Furthermore, the algorithm temporarily stores subpaths to check for their existence in other paths. Thus, the auxiliary space scales linearly with the length of the paths. Therefore, the overall auxiliary space complexity is O(N).

Optimal Solution

Approach

The optimal strategy uses a process of elimination and intelligent searching to find the longest common path. It's like searching for a specific road that exists in several different maps, but instead of checking every road one by one, we use a clever method to narrow down the possibilities.

Here's how the algorithm would work step-by-step:

First, figure out the possible lengths of the common path by looking at the shortest path. The longest possible common path can be at most as long as the shortest individual path.
Imagine that we have some candidate length of a path. Now we need to see if that length really exists in all of the provided paths.
For a given length, take each of the paths, and collect all subpaths with that particular length.
Now check if there exists at least one subpath that is common among *all* paths.
If a common subpath is found, then we know that length is valid. If no common subpath is found, the length is too long.
Use a process of elimination similar to a binary search. Start with the middle length. If it's valid, try a larger length. If not, try a shorter one.
Keep doing this until you find the longest length for which a common subpath exists. This is your final answer.

Code Implementation

def longest_common_subpath(number_of_paths, paths):
    shortest_path_length = min(len(path) for path in paths)
    low = 1
    high = shortest_path_length
    longest_common_length = 0

    while low <= high:
        mid = (low + high) // 2

        # Check if a common subpath of length mid exists.
        if is_common_subpath_present(paths, mid):

            # If it exists, increase the lower bound.
            longest_common_length = mid
            low = mid + 1
        else:

            # Otherwise, decrease the upper bound.
            high = mid - 1

    return longest_common_length

def is_common_subpath_present(paths, subpath_length):
    if subpath_length == 0:
        return True

    first_path_subpaths = set()
    for i in range(len(paths[0]) - subpath_length + 1):
        first_path_subpaths.add(tuple(paths[0][i:i + subpath_length]))

    # We iterate through the rest of the paths.
    for path in paths[1:]:
        current_path_subpaths = set()
        for i in range(len(path) - subpath_length + 1):
            current_path_subpaths.add(tuple(path[i:i + subpath_length]))

        # We need to find the intersection to update.
        first_path_subpaths = first_path_subpaths.intersection(current_path_subpaths)

        # If no common subpaths are found, return immediately.
        if not first_path_subpaths:
            return False

    return True

Big(O) Analysis

Time Complexity

O(n*m*log(L)) – Let n be the number of paths, m be the average length of a path, and L be the length of the shortest path. The binary search for the length of the longest common subpath takes O(log(L)) time. Inside the binary search, we iterate through each of the n paths. For each path, we extract all possible subpaths of the current length, which takes O(m) time. Checking if a subpath exists in all n paths can be done using a hash set which takes O(n*m) time in total. Therefore the runtime is approximately O(n*m*log(L)).

Space Complexity

O(N) – The dominant space complexity stems from storing subpaths of a given length in step 3. In the worst case, each path might have almost all possible subpaths of a particular length, leading to the creation of lists to store these subpaths for each of the input paths. If we let N be the total number of elements across all paths, in the worst case we might be storing O(N) subpaths in a temporary data structure (like a set or list). The other operations like binary search use a constant amount of space, hence the total auxiliary space used is O(N).

Edge Cases

Case	How to Handle
paths is null or empty	Return 0 immediately as there are no paths to compare, implying no common subpath.
paths contains an empty path	Return 0 immediately, as an empty path means no subpath can be common among all paths.
paths contains a single path	Return the length of the single path as the longest common subpath is the path itself.
All paths are identical	Return the length of any path, as they are all the same.
No common subpath exists	Binary search should converge to a length of 0, correctly indicating no common subpath.
paths have vastly different lengths	The binary search's validation step needs to efficiently check for subpath existence, potentially needing optimization via rolling hash.
Large integer values in paths (potential overflow in hash function)	Use a modular arithmetic approach in the rolling hash function to prevent integer overflow, choosing a large prime number.
maxPathLength is very large (potential memory constraints)	Optimize the rolling hash implementation for memory efficiency, such as only storing hash values for a relevant subset of lengths during the binary search.

paths is null or empty

How to Handle:

Return 0 immediately as there are no paths to compare, implying no common subpath.

paths contains an empty path

How to Handle:

Return 0 immediately, as an empty path means no subpath can be common among all paths.

paths contains a single path

How to Handle:

Return the length of the single path as the longest common subpath is the path itself.

All paths are identical

How to Handle:

Return the length of any path, as they are all the same.

No common subpath exists

How to Handle:

Binary search should converge to a length of 0, correctly indicating no common subpath.

paths have vastly different lengths

How to Handle:

The binary search's validation step needs to efficiently check for subpath existence, potentially needing optimization via rolling hash.

Large integer values in paths (potential overflow in hash function)

How to Handle:

Use a modular arithmetic approach in the rolling hash function to prevent integer overflow, choosing a large prime number.

maxPathLength is very large (potential memory constraints)

How to Handle:

Optimize the rolling hash implementation for memory efficiency, such as only storing hash values for a relevant subset of lengths during the binary search.