1923. Longest Common Subpath

HardArrayBinary SearchSuffix ArrayHash FunctionRolling Hash

Problem Description

This problem is about finding the longest subpath that is common to every friend's travel path in a fully connected country. Here's the scenario in simple terms:

There are n cities, and each city is connected to every other city.
There are m friends, each with their travel paths represented as sequences of city numbers.
The same city number can appear multiple times in a path, but not consecutively.
A subpath is defined as a contiguous sequence of cities in a travel path.

The goal is to determine the length of the longest subpath that all friends' paths have in common. If no common subpath exists among all friends, the result should be 0.

Intuition

To solve this problem, we use a binary search to find the maximum length of a common subpath combined with rolling hash for subpath identification. To understand the intuition behind the solution, consider these steps:

Binary Search for Subpath Length: Since the subpath length can range from 0 to the length of the shortest path, we perform a binary search within this range. By finding the midpoint in each iteration, we can check if the current length exists as a subpath in all friends' paths. If it does, we try a longer length; if not, we shorten the search.
Rolling Hash to Compare Subpaths: To efficiently check if a subpath exists in all friends' paths, we use a rolling hash function. This computes a hash value for each subpath, which allows for constant-time comparison between subpaths.
Avoiding Hash Collisions: As we use modulo arithmetic with a large prime number to minimize hash collisions, the rolling hash function is less likely to give the same hash for different subpaths.
Using Counters: A Counter keeps track of how many times a particular hash appears in the list of subpaths of all friends' paths. If the count equals the number of friends (m), the subpath represented by that hash is common to all paths.
Deciding the Common Subpath Length: The binary search continues until we find the longest subpath length that appears in all friends' paths.

This method efficiently identifies the longest common subpath shared among every friend's path, by iteratively narrowing down the possible lengths and verifying existence using a consistent hashing technique.

Learn more about Binary Search patterns.

Solution Approach

The implementation of the solution uses function longestCommonSubpath, carrying out a binary search to zero in on the length of the longest common subpath. Here is a walkthrough of the method applied, revealing how algorithms, data structures, and patterns are put to use:

Pre-computation of Powers: Before executing the binary search, we compute powers of the base (base) used in the rolling hash function, storing them in an array p. The base is chosen as a large prime number for hash distribution. This pre-computation speeds up the subsequent hash calculations for different subpaths.
Rolling Hash Function: The function check(k) computes a rolling hash for each subpath of length k in each friend's path. This is achieved with the formula (h[j] - h[i - 1] * p[j - i + 1]) % mod, where h is the prefix hash array and mod is a large prime number for modulo operation to avoid overflow and collisions.
Counter for Hash Values: A Counter cnt is used to track how many times each hash appears across all paths. This counter helps identify if a hash, which represents a subpath of length k, is common to all friends' paths by comparing the count to the total number of friends m.
Using A Set to Avoid Duplicates: Inside check(k), a set vis is employed for each friend's path hashes to ensure the same subpath is not counted multiple times for a single friend, which would misrepresent the actual commonality of that subpath.
Binary Search: We initiate the binary search between 0 and the length of the shortest path (inclusive) to find the longest length k for which check(k) returns True. The condition in the binary search contrasts the max count value in cnt to m to determine if a common subpath of length k exists. If it is successful, we increase the lower boundary l to mid. Otherwise, we decrease the upper boundary r to mid - 1. We continue this process until l and r converge to the maximum value of k.
Returning the Result: After the binary search concludes, the variable l holds the length of the longest common subpath, which is the answer we return.

By leveraging the efficiency of binary search and the uniqueness of hash values produced by a rolling hash function, the function longestCommonSubpath determines the maximum length of a subpath common to all friends' paths with optimized time complexity.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a simple example:

Suppose we have 3 cities {1, 2, 3} and 2 friends with the following travel paths:

Friend 1: {1, 2, 3, 2}
Friend 2: {2, 3, 2, 1}

We are interested in finding the longest subpath that is common to every friend's travel path.

Pre-computation of Powers:
- Assume our base for hashing is a prime number, let's say 101. We pre-compute the powers of this base up to the length of the shortest path (here both paths are of the same length, so we compute 4 powers).
Binary Search Initiation:
- The range of possible subpath lengths is [0, 4]. We start with a binary search between these values.
First Iteration of Binary Search:
- The mid-point of [0, 4] is 2, so we check for subpaths of length 2 (k = 2).
Rolling Hash Calculation:
- Compute the rolling hash for each subpath of length 2 in both friends' paths:
  - Friend 1 would have subpaths {1, 2}, {2, 3}, {3, 2}.
  - Friend 2 would have subpaths {2, 3}, {3, 2}, {2, 1}.
- Let's calculate an example hash with a fake hash function for demonstrating purposes (actual hashes would involve the precomputed powers and modulo operations to avoid collisions):
  - Hash for {1, 2} might be 5.
  - Hash for {2, 3} might be 11.
  - Hash for {3, 2} might be 11.
  - Hash for {2, 1} might be 8.
- We notice that the subpath {2, 3} with hash 11 is common to both friends.
Counter Update and Set Utilization:
- A counter cnt would count each unique hash per friend. Since hash 11 appears in both friends' paths and is the only one that does, it has the highest count, which is equal to the number of friends m = 2.
- The set vis ensures that we only count {2, 3} once for Friend 1 although it appears twice.
Concluding the Binary Search:
- Since we found a common subpath of the tested length 2, we now look for a longer common subpath by updating our binary search range to [3, 4].
- Next mid-point is 3.5 (we consider 3 for subpath length). We repeat steps 4 and 5 for length 3:
  - Friend 1 would have subpaths {1, 2, 3} and {2, 3, 2}.
  - Friend 2 would have subpaths {2, 3, 2} and {3, 2, 1}.
  - No common subpaths of length 3 are found in both friends' paths.
- Since there is no common subpath of length 3, we update our binary search range to [2, 2].
Returning the Result:
- The binary search range [2, 2] indicates that the longest common subpath length is 2, which is the solution that the function longestCommonSubpath would return.

In this example, the longest common subpath that exists in both friends' paths is of length 2, and it consists of the sequence of cities {2, 3}. This example demonstrates how binary search, along with a rolling hash, can be used to efficiently find the longest common subpath among paths taken by different friends.

Solution Implementation

1from collections import Counter
2from typing import List
3
4class Solution:
5    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:
6        # Helper function to check if there's a common subpath of length k
7        def is_common_subpath_length_k(k: int) -> bool:
8            hash_counts = Counter()
9            for h in hash_values:
10                visited = set()
11                for i in range(1, len(h) - k + 1):
12                    j = i + k - 1
13                    # Calculate the hash for the current subpath
14                    current_hash = (h[j] - h[i - 1] * powers[j - i + 1]) % mod
15                    # Update the hash_counts only once for each unique subpath
16                    if current_hash not in visited:
17                        visited.add(current_hash)
18                        hash_counts[current_hash] += 1
19            # Check if all paths have the subpath of length k
20            return max(hash_counts.values()) == number_of_paths
21
22        number_of_paths = len(paths)
23        max_path_length = max(len(path) for path in paths)
24        base = 133331
25        mod = 2**64 + 1
26      
27        # Precompute powers of the base modulo mod to use later for rolling hashes
28        powers = [0] * (max_path_length + 1)
29        powers[0] = 1
30        for i in range(1, len(powers)):
31            powers[i] = powers[i - 1] * base % mod
32      
33        # Precompute the hashes for all paths
34        hash_values = []
35        for path in paths:
36            path_length = len(path)
37            h = [0] * (path_length + 1)
38            for i, value in enumerate(path, 1):
39                h[i] = (h[i - 1] * base % mod) + value
40            hash_values.append(h)
41      
42        # Binary search to find the maximum length of common subpath
43        left, right = 0, min(len(path) for path in paths)
44        while left < right:
45            mid = (left + right + 1) // 2
46            if is_common_subpath_length_k(mid):
47                left = mid
48            else:
49                right = mid - 1
50      
51        # Return the maximum length of common subpath found
52        return left
53

1import java.util.HashMap;
2import java.util.Map;
3
4class Solution {
5    private static final int MAX_N = 100010;
6    private long[] hashValue = new long[MAX_N];
7    private long[] power = new long[MAX_N];
8    private int[][] paths;
9    private Map<Long, Integer> countMap = new HashMap<>();
10    private Map<Long, Integer> prefixMap = new HashMap<>();
11
12    // Function to find the length of the longest common subpath
13    public int longestCommonSubpath(int n, int[][] paths) {
14        int left = 0, right = MAX_N;
15        // Find the shortest path length among all paths
16        for (int[] path : paths) {
17            right = Math.min(right, path.length);
18        }
19        this.paths = paths;
20        // Perform binary search to find the maximum length of common subpath
21        while (left < right) {
22            int mid = (left + right + 1) >> 1;
23            if (check(mid)) {
24                left = mid;
25            } else {
26                right = mid - 1;
27            }
28        }
29        return left;
30    }
31
32    // Helper method to check if there is a common subpath of given length
33    private boolean check(int length) {
34        countMap.clear();
35        prefixMap.clear();
36        power[0] = 1;
37        // Iterate over each path
38        for (int j = 0; j < paths.length; ++j) {
39            int pathLength = paths[j].length;
40            // Precompute powers and hash values for the current path
41            for (int i = 1; i <= pathLength; ++i) {
42                power[i] = power[i - 1] * 133331;
43                hashValue[i] = hashValue[i - 1] * 133331 + paths[j][i - 1];
44            }
45            // Traverse the path and update maps with hash values for each subpath of given length
46            for (int i = length; i <= pathLength; ++i) {
47                long val = getHash(i - length + 1, i);
48                if (!prefixMap.containsKey(val) || prefixMap.get(val) != j) {
49                    prefixMap.put(val, j);
50                    countMap.put(val, countMap.getOrDefault(val, 0) + 1);
51                }
52            }
53        }
54        // Find the maximum frequency of common subpaths and check if it equals the number of paths
55        for (int val : countMap.values()) {
56            if (val == paths.length) {
57                return true;
58            }
59        }
60        return false;
61    }
62
63    // Helper method to get the hash value for a subpath
64    private long getHash(int left, int right) {
65        return hashValue[right] - hashValue[left - 1] * power[right - left + 1];
66    }
67}
68

1#include <vector>
2#include <map>
3
4class Solution {
5private:
6    static const int MAX_N = 100010;
7    long long hashValue[MAX_N];
8    long long power[MAX_N];
9    std::vector<std::vector<int>> paths;
10    std::map<long long, int> countMap;
11    std::map<long long, int> prefixMap;
12
13    // Helper method to get the hash value for a subpath
14    long long GetHash(int left, int right) {
15        return hashValue[right] - hashValue[left - 1] * power[right - left + 1];
16    }
17
18    // Helper method to check if there is a common subpath of given length
19    bool Check(int length) {
20        countMap.clear();
21        prefixMap.clear();
22        power[0] = 1;
23
24        // Iterate over each path
25        for(int j = 0; j < paths.size(); ++j) {
26            int pathLength = paths[j].size();
27            hashValue[0] = 0;
28
29            // Precompute powers and hash values for the current path
30            for(int i = 1; i <= pathLength; ++i) {
31                power[i] = power[i - 1] * 133331;
32                hashValue[i] = hashValue[i - 1] * 133331 + paths[j][i - 1];
33            }
34
35            // Traverse the path and update maps with hash values for each subpath of given length
36            for(int i = length; i <= pathLength; ++i) {
37                long long val = GetHash(i - length + 1, i);
38                if(prefixMap.find(val) == prefixMap.end() || prefixMap[val] != j) {
39                    prefixMap[val] = j;
40                    countMap[val] = countMap[val] + 1;
41                }
42            }
43        }
44
45        // Find the maximum frequency of common subpaths and check if it equals the number of paths
46        for(auto &entry : countMap) {
47            if(entry.second == paths.size()) {
48                return true;
49            }
50        }
51
52        return false;
53    }
54
55public:
56    // Function to find the length of the longest common subpath
57    int LongestCommonSubpath(int n, std::vector<std::vector<int>>& paths) {
58        int left = 0, right = MAX_N;
59
60        // Find the shortest path length among all paths
61        for(const auto& path : paths) {
62            right = std::min(right, (int)path.size());
63        }
64      
65        this->paths = paths;
66
67        // Perform binary search to find the maximum length of common subpath
68        while(left < right) {
69            int mid = (left + right + 1) / 2;
70            if(Check(mid)) {
71                left = mid;
72            } else {
73                right = mid - 1;
74            }
75        }
76
77        return left;
78    }
79};
80

1// Constants.
2const MAX_N = 100010;
3
4// Global variables.
5let hashValue: number[] = new Array(MAX_N).fill(0);
6let power: number[] = new Array(MAX_N).fill(0);
7let paths: number[][];
8let countMap: Map<number, number> = new Map();
9let prefixMap: Map<number, number> = new Map();
10
11/**
12 * Calculate the length of the longest common subpath across all paths.
13 * @param n The number of cities.
14 * @param inputPaths An array of arrays where each subarray represents a path through cities.
15 * @returns The maximum length of a common subpath.
16 */
17function longestCommonSubpath(n: number, inputPaths: number[][]): number {
18    let left: number = 0;
19    let right: number = MAX_N;
20
21    // Find the shortest path length among all paths.
22    for (let path of inputPaths) {
23        right = Math.min(right, path.length);
24    }
25    paths = inputPaths;
26
27    // Perform binary search to find the maximum length of common subpath.
28    while (left < right) {
29        let mid: number = Math.floor((left + right + 1) / 2);
30        if (check(mid)) {
31            left = mid;
32        } else {
33            right = mid - 1;
34        }
35    }
36    return left;
37}
38
39/**
40 * Helper method to check if there is a common subpath of a given length.
41 * @param length The length of the subpath to check for commonality.
42 * @returns A boolean indicating if a common subpath of the given length exists.
43 */
44function check(length: number): boolean {
45    countMap.clear();
46    prefixMap.clear();
47    power[0] = 1;
48
49    // Iterate over each path.
50    for (let j: number = 0; j < paths.length; ++j) {
51        let pathLength: number = paths[j].length;
52
53        // Precompute powers and hash values for the current path.
54        for (let i: number = 1; i <= pathLength; ++i) {
55            power[i] = power[i - 1] * 133331;
56            hashValue[i] = hashValue[i - 1] * 133331 + paths[j][i - 1];
57        }
58
59        // Traverse the path and update maps with hash values for each subpath of the given length.
60        for (let i: number = length; i <= pathLength; ++i) {
61            let hash: number = getHash(i - length + 1, i);
62            if (!prefixMap.has(hash) || prefixMap.get(hash) !== j) {
63                prefixMap.set(hash, j);
64                countMap.set(hash, (countMap.get(hash) || 0) + 1);
65            }
66        }
67    }
68
69    // Find the maximum frequency of common subpaths and check if it equals the number of paths.
70    for (let val of countMap.values()) {
71        if (val === paths.length) {
72            return true;
73        }
74    }
75    return false;
76}
77
78/**
79 * Helper method to get the hash value for a subpath.
80 * @param left The starting index of the subpath.
81 * @param right The ending index of the subpath.
82 * @returns The hash value of the specified subpath.
83 */
84function getHash(left: number, right: number): number {
85    return hashValue[right] - hashValue[left - 1] * power[right - left + 1];
86}
87

Time and Space Complexity

Time Complexity

The time complexity has several components derived from different parts of the code.

Initializing the power array p: This loop runs for mx+1 iterations, where mx is the length of the longest path in paths. So this part is O(mx).
Computing hashes for each path: For each path in paths (and there are m = len(paths) such paths), we calculate the prefix hash in a loop that runs for k + 1 iterations (k being the length of the individual path). The overall complexity for this part would be O(m*mx) since O(k+1) is bounded by the length of the longest path.
The binary search: The binary search runs O(log(mx)) times (mx being the maximum length of a path).
Inside the binary search, the check(k: int) function is called, which iterates over each of m paths and for each path goes through a loop of up to O(mx - k) iterations where mx is the maximum length of a path in paths and k the current guess for the binary search. But since we only add a hash to vis if it has not been seen before, and there are at most mx unique hashes, we can argue this costs O(mx) time per path. Since m paths are considered, each call to check function costs O(m*mx).

Combining these, the time complexity of the binary search dominates the overall time complexity. The total time complexity is O(m * mx * log(mx)).

Space Complexity

The space complexity of the code also comprises several parts:

The power array p consumes O(mx) space.
Storing hashes hh for each path takes O(m * mx), as for each of the m paths we store an array of hashes of length proportional to the path length mx.
The check function uses a Counter and a set, which in the worst-case could store up to O(mx) unique hashes for each path (across all paths in hh). Thus, the space needed may be up to O(mx).

Combining these parts, the dominant space complexity is from storing the hashes hh. Given this, the overall space complexity is O(m * mx).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know