LeetCode 1940. Longest Common Subsequence Between Sorted Arrays Solution in Java, C++, Python & More | Explanation + Code

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 cnt of length 101 to record the number of occurrences of each element.

Since each array in 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 arrays.

Therefore, we can traverse each array in arrays and count the number of occurrences of each element. Finally, traverse each element of cnt from smallest to largest. If the number of occurrences is equal to the length of 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.

PythonJavaC++GoTypeScriptJavaScript

class Solution: def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]: cnt = [0] * 101 for row in arrays: for x in row: cnt[x] += 1 return [x for x, v in enumerate(cnt) if v == len(arrays)](code-box)

class Solution { public List<Integer> longestCommonSubsequence(int[][] arrays) { int[] cnt = new int[101]; for (var row : arrays) { for (int x : row) { ++cnt[x]; } } List<Integer> ans = new ArrayList<>(); for (int i = 0; i < 101; ++i) { if (cnt[i] == arrays.length) { ans.add(i); } } return ans; } }(code-box)

class Solution { public: vector<int> longestCommonSubsequence(vector<vector<int>>& arrays) { int cnt[101]{}; for (const auto& row : arrays) { for (int x : row) { ++cnt[x]; } } vector<int> ans; for (int i = 0; i < 101; ++i) { if (cnt[i] == arrays.size()) { ans.push_back(i); } } return ans; } };(code-box)

func longestCommonSubsequence(arrays [][]int) (ans []int) { cnt := [101]int{} for _, row := range arrays { for _, x := range row { cnt[x]++ } } for x, v := range cnt { if v == len(arrays) { ans = append(ans, x) } } return }(code-box)

function longestCommonSubsequence(arrays: number[][]): number[] { const cnt: number[] = Array(101).fill(0); for (const row of arrays) { for (const x of row) { ++cnt[x]; } } const ans: number[] = []; for (let i = 0; i < 101; ++i) { if (cnt[i] === arrays.length) { ans.push(i); } } return ans; }(code-box)

/** * @param {number[][]} arrays * @return {number[]} */ var longestCommonSubsequence = function (arrays) { const cnt = Array(101).fill(0); for (const row of arrays) { for (const x of row) { ++cnt[x]; } } const ans = []; for (let i = 0; i < 101; ++i) { if (cnt[i] === arrays.length) { ans.push(i); } } return ans; };(code-box)