Leetcode 1940 Longest Common Subsequence Between Sorted Arrays

Problem statement

https://leetcode.com/problems/longest-common-subsequence-between-sorted-arrays/

Solution

Actually what is asked is to find intersection of several given sets, because number in our arrays are increasing. So, we just find intersection and then sort our data.

Complexity

Time complexity is O(N + x*log x), where X is total length of all sequences and x is the lengt of answer (which is not bigger than min(len(A[i]))

Code

class Solution:
    def longestCommonSubsequence(self, A):
        start = set(A[0])
        for seq in A[1:]:
            start &= set(seq)
        return sorted(start)

Remark

Or we can just count numbers and take only those who have frequency len(A).