# 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 between 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

• class Solution {
public List<Integer> longestCommomSubsequence(int[][] arrays) {
Map<Integer, Integer> counter = new HashMap<>();
for (int[] array : arrays) {
for (int e : array) {
counter.put(e, counter.getOrDefault(e, 0) + 1);
}
}
int n = arrays.length;
List<Integer> res = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
if (entry.getValue() == n) {
}
}
return res;
}
}

• class Solution {
public:
vector<int> longestCommomSubsequence(vector<vector<int>>& arrays) {
unordered_map<int, int> counter;
vector<int> res;
int n = arrays.size();
for (auto array : arrays) {
for (auto e : array) {
counter[e] += 1;
if (counter[e] == n) {
res.push_back(e);
}
}
}
return res;
}
};

• class Solution:
def longestCommomSubsequence(self, arrays: List[List[int]]) -> List[int]:
n = len(arrays)
counter = defaultdict(int)
for array in arrays:
for e in array:
counter[e] += 1
return [e for e, count in counter.items() if count == n]


• func longestCommomSubsequence(arrays [][]int) []int {
counter := make(map[int]int)
n := len(arrays)
var res []int
for _, array := range arrays {
for _, e := range array {
counter[e]++
if counter[e] == n {
res = append(res, e)
}
}
}
return res
}

• /**
* @param {number[][]} arrays
* @return {number[]}
*/
var longestCommonSubsequence = function (arrays) {
const m = new Map();
const rs = [];
const len = arrays.length;
for (let i = 0; i < len; i++) {
for (let j = 0; j < arrays[i].length; j++) {
m.set(arrays[i][j], (m.get(arrays[i][j]) || 0) + 1);
if (m.get(arrays[i][j]) === len) rs.push(arrays[i][j]);
}
}
return rs;
};