Code Implementation

class Solution:
    def longestCommonSubsequence(self, arrays):
        if not arrays:
            return []
        res = []
        # Use the first array as reference
        from collections import Counter
        common = set(arrays[0])
        for arr in arrays[1:]:
            common = common & set(arr)
        # Now, build the LCS by checking order in the first array
        for num in arrays[0]:
            if num in common:
                res.append(num)
        return res
      

class Solution {
public:
    vector<int> longestCommonSubsequence(vector<vector<int>>& arrays) {
        if (arrays.empty()) return {};
        unordered_set<int> common(arrays[0].begin(), arrays[0].end());
        for (int i = 1; i < arrays.size(); ++i) {
            unordered_set<int> next(arrays[i].begin(), arrays[i].end());
            unordered_set<int> intersection;
            for (int num : common) {
                if (next.count(num)) intersection.insert(num);
            }
            common = intersection;
        }
        vector<int> res;
        for (int num : arrays[0]) {
            if (common.count(num)) res.push_back(num);
        }
        return res;
    }
};
      

class Solution {
    public List<Integer> longestCommonSubsequence(List<List<Integer>> arrays) {
        if (arrays.size() == 0) return new ArrayList<>();
        Set<Integer> common = new HashSet<>(arrays.get(0));
        for (int i = 1; i < arrays.size(); i++) {
            Set<Integer> next = new HashSet<>(arrays.get(i));
            common.retainAll(next);
        }
        List<Integer> res = new ArrayList<>();
        for (int num : arrays.get(0)) {
            if (common.contains(num)) {
                res.add(num);
            }
        }
        return res;
    }
}
      

var longestCommonSubsequence = function(arrays) {
    if (arrays.length === 0) return [];
    let common = new Set(arrays[0]);
    for (let i = 1; i < arrays.length; i++) {
        let next = new Set(arrays[i]);
        let intersection = new Set();
        for (let num of common) {
            if (next.has(num)) intersection.add(num);
        }
        common = intersection;
    }
    let res = [];
    for (let num of arrays[0]) {
        if (common.has(num)) res.push(num);
    }
    return res;
};
      

Problem Description

You are given a list of sorted arrays, arrays, where each element is a sorted list of integers. Your task is to find the longest subsequence (in order) that is common to all the arrays. The subsequence must appear in the same order in each array, but the elements do not have to be consecutive. Each element in the subsequence must be present in every array, and you cannot reuse elements.

Constraints:

• There is always one valid solution.
• Elements must not be reused.
• All arrays are sorted in strictly increasing order.
• Return the subsequence as a list of integers.

Thought Process

At first glance, the problem looks similar to the classic "Longest Common Subsequence" (LCS) problem for two strings, but here we have multiple arrays instead of just two. The brute-force approach would be to generate all possible subsequences of the first array and check if each one exists (in order) in all other arrays. However, this quickly becomes infeasible as the number of possible subsequences grows exponentially with the array's length.

Given that all arrays are sorted and strictly increasing, we can take advantage of this property. If an element appears in all arrays, and the arrays are sorted, then the relative order is already preserved. So, instead of looking for the "longest" common subsequence, we can look for the list of elements that are present in every array, and collect them in order as they appear in the first array.

This shifts our approach from generating all subsequences to simply finding the intersection of all arrays, and then outputting those elements in the order they appear in the first array.

Solution Approach

To solve the problem efficiently, we can follow these steps:

1. Find the intersection of all arrays:
   • Start with the set of elements in the first array.
   • Iteratively intersect this set with each subsequent array.
   • This will give us the set of elements that appear in every array.
2. Preserve the order:
   • Since the problem asks for a subsequence in the same order as the arrays, we need to output the elements in the order they appear in the first array.
   • Iterate through the first array and collect elements that are present in the intersection set.

We use a set for fast O(1) lookups when checking if an element is common to all arrays. This avoids the need for nested loops and reduces the overall complexity.

Example Walkthrough

Consider the input:

    arrays = [
      [1, 3, 4, 5, 7],
      [2, 3, 5, 7, 9],
      [1, 3, 5, 6, 7, 10]
    ]
    

• Start with the set of the first array: {1, 3, 4, 5, 7}
• Intersect with the second array: {2, 3, 5, 7, 9} → intersection is {3, 5, 7}
• Intersect with the third array: {1, 3, 5, 6, 7, 10} → intersection is {3, 5, 7}
• Now iterate through the first array and collect elements in the intersection set, in order: 3, 5, 7

The final answer is [3, 5, 7].

Time and Space Complexity

Brute-force approach:

• Generating all subsequences of the first array is O(2^n), where n is the length of the array.
• For each subsequence, checking if it is a subsequence of all other arrays could be O(m * n), where m is the number of arrays.
• This is not scalable for large inputs.

• Building the intersection set takes O(m * n), where m is the number of arrays and n is the average length of the arrays.
• Iterating through the first array to collect results is O(n).
• Total time complexity: O(m * n)
• Space complexity: O(n) for storing the intersection set and the result.

This is efficient and suitable for the given constraints.

Summary

By leveraging the fact that all arrays are sorted and strictly increasing, we can reduce the problem to finding the intersection of all arrays and outputting the common elements in order. This approach is much more efficient than brute-force and takes advantage of fast set operations. The key insight is recognizing that order is preserved by the sorted property, allowing us to avoid expensive dynamic programming or recursion.