Array
Hash Table
Counting
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
Python3 Java C++ Go JavaScript
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 ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 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 ) {
res . add ( entry . getKey ());
}
}
return res ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14 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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 /**
* @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 ;
};
Solution 2
Python3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution :
def longestCommomSubsequence ( self , arrays : List [ List [ int ]]) -> List [ int ]:
def common ( l1 , l2 ):
i , j , n1 , n2 = 0 , 0 , len ( l1 ), len ( l2 )
res = []
while i < n1 and j < n2 :
if l1 [ i ] == l2 [ j ]:
res . append ( l1 [ i ])
i += 1
j += 1
elif l1 [ i ] > l2 [ j ]:
j += 1
else :
i += 1
return res
n = len ( arrays )
for i in range ( 1 , n ):
arrays [ i ] = common ( arrays [ i - 1 ], arrays [ i ])
return arrays [ n - 1 ]
GitHub