Longest Common Subsequence Between Sorted Arrays

To find the longest common subsequence (LCS) between all the arrays, you can start by comparing the first two arrays to find their LCS. Then, take the result and compare it with the next array to find the LCS, and continue this process until you have compared all arrays. Here’s a step-by-step approach to solving this problem:

  1. Initialize the LCS: Start by assuming the LCS is the first array, since the LCS of all arrays will be a subset of any individual array.

  2. Iterate Through the Arrays: Iterate through the rest of the arrays, comparing each one with the current LCS to find the new LCS.

  3. Compare Two Arrays: To compare two arrays and find their LCS, you can use two pointers to iterate through the arrays, adding common elements to the new LCS.

  4. Continue Until All Arrays are Processed: Repeat this process until you have compared the current LCS with all arrays.

  5. Return the LCS: Return the final LCS.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
        lcs = arrays[0]

        for array in arrays[1:]:
            new_lcs = []
            i = j = 0

            while i < len(lcs) and j < len(array):
                if lcs[i] == array[j]:
                    new_lcs.append(lcs[i])
                    i += 1
                    j += 1
                elif lcs[i] < array[j]:
                    i += 1
                else:
                    j += 1

            lcs = new_lcs

        return lcs

This code efficiently finds the LCS between all the arrays by comparing them one by one, ensuring the result is the longest common subsequence between all the arrays, and adheres to the constraints provided.