Leetcode # 1940. Longest Common Subsequence Between Sorted Arrays

Problem

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

Solution 1

Time Complexity: O(sum(len(a) for a in arrays)) * 2 (for array in arrays for n in array + for k in keys)
Space Complexity: O(sum(len(a) for a in arrays))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
    nums = Counter()
    for array in arrays:
      for n in array:
        nums[n] += 1
    keys = sorted(nums.keys())
    ret = []
    for k in keys:
      if nums[k] == len(arrays):
        ret.append(k)
    return ret

Solution 2

找到在全部 array 都存在的數 ⇔ 只要有一個 array 不存在該數就將其移除

s = min(len(a) for a in arrays)
m = max(len(a) for a in arrays)

Time Complexity:
O(len(a)) + O(s * (len(a) – 1) * log(m)) = O(len(a) * s * log(m))
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
    shortest_array, shortest_array_i = arrays[0], 0
    for i, a in enumerate(arrays[1:]):
      if len(a) < len(shortest_array):
        shortest_array = a
        shortest_array_i = i + 1
    
    def binary_search(array, target):
      left, right = 0, len(array) - 1
      while left <= right:
        mid = (left + right) // 2
        if array[mid] < target:
          left = mid + 1
        elif array[mid] > target:
          right = mid - 1
        else: return True
      return False

    longest_common_subseq = []
    for n in shortest_array:
      n_is_common = True
      for i, a in enumerate(arrays):
        if i == shortest_array_i: continue
        if not binary_search(a, n):
          n_is_common = False
          break
      if n_is_common:
        longest_common_subseq.append(n)
        
    return longest_common_subseq

Last Updated on 2024/06/09 by A1go