We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Common Subsequence Between Sorted Arrays

Number: 2071

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an array of integer arrays where each subarray is sorted in strictly increasing order, return an integer array representing the longest common subsequence among all the arrays. A subsequence is derived by deleting some elements (possibly none) without changing the order of the remaining elements.

Key Insights

  • Since each array is sorted in strictly increasing order, any common element found in all arrays will naturally preserve order.
  • The problem reduces to finding the intersection of all arrays while preserving the order present in the first array.
  • Using set intersections simplifies the process of finding common elements.
  • The intersection preserves the elements but not their order – thus, iterating through the first array helps recreate the correct ordered subsequence.
  • This approach works efficiently due to the constraints, where arrays have modest lengths.

Space and Time Complexity

Time Complexity: O(n * m) where n is the number of arrays and m is the maximum length of an array. Space Complexity: O(m) for storing the intermediate sets.

Solution

The solution leverages set intersections to find common elements among all arrays. Start by converting the first array into a set, then iteratively intersect this set with the sets derived from the subsequent arrays. Finally, rebuild the result by iterating over the first array, including only those elements found in the intersection. This method is facilitated by the fact that the arrays are sorted in strictly increasing order, ensuring that the order maintained in the first array will be valid for the common subsequence.

Code Solutions

# Function to find the longest common subsequence among sorted arrays
def longest_common_subsequence(arrays):
    # Initialize common_set with the first array's elements
    common_set = set(arrays[0])
    # Intersect with each remaining array's elements
    for arr in arrays[1:]:
        common_set &= set(arr)
    # Build the result preserving the order of the first array
    result = [num for num in arrays[0] if num in common_set]
    return result

# Example usage:
arrays = [[1, 3, 4], [1, 4, 7, 9]]
print(longest_common_subsequence(arrays))  # Output: [1, 4]
← Back to All Questions