1940. Longest Common Subsequence Between Sorted Arrays π
Description
Given an array of integer arrays arrays
where each arrays[i]
is sorted in strictly increasing order, return an integer array representing the longest common subsequence among all the arrays.
A subsequence is a sequence that can be derived from another sequence by deleting some elements (possibly none) without changing the order of the remaining elements.
Example 1:
Input: arrays = [[1,3,4], [1,4,7,9]] Output: [1,4] Explanation: The longest common subsequence in the two arrays is [1,4].
Example 2:
Input: arrays = [[2,3,6,8], [1,2,3,5,6,7,10], [2,3,4,6,9]] Output: [2,3,6] Explanation: The longest common subsequence in all three arrays is [2,3,6].
Example 3:
Input: arrays = [[1,2,3,4,5], [6,7,8]] Output: [] Explanation: There is no common subsequence between the two arrays.
Constraints:
2 <= arrays.length <= 100
1 <= arrays[i].length <= 100
1 <= arrays[i][j] <= 100
arrays[i]
is sorted in strictly increasing order.
Solutions
Solution 1: Counting
We note that the range of elements is \([1, 100]\), so we can use an array \(\textit{cnt}\) of length \(101\) to record the number of occurrences of each element.
Since each array in \(\textit{arrays}\) is strictly increasing, the elements of the common subsequence must be monotonically increasing, and the number of occurrences of these elements must be equal to the length of \(\textit{arrays}\).
Therefore, we can traverse each array in \(\textit{arrays}\) and count the number of occurrences of each element. Finally, traverse each element of \(\textit{cnt}\) from smallest to largest. If the number of occurrences is equal to the length of \(\textit{arrays}\), then this element is one of the elements of the common subsequence, and we add it to the answer array.
After the traversal, return the answer array.
The time complexity is \(O(M + N)\), and the space complexity is \(O(M)\). Here, \(M\) is the range of elements, and in this problem, \(M = 101\), and \(N\) is the total number of elements in the arrays.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|