What is the time complexity of LeetCode 1940. Longest Common Subsequence Between Sorted Arrays?

The Python solution on this page runs in O(M + N).

What is the space complexity of LeetCode 1940. Longest Common Subsequence Between Sorted Arrays?

The Python solution on this page uses O(M) auxiliary space.

Longest Common Subsequence Between Sorted Arrays — LeetCode 1940 Python Solution

MediumLeetCode PremiumArrayHash TableCounting

Problem: #1940
Pattern: Hash Map
Reading time: 2 min
Source: leetcode.com

The problem

Given an array of integer arrays arrays where each arrays[i] is sorted in strictly increasing order, return an integer array representing the longest common subsequence among all the arrays. A subsequence is a sequence that can be derived from another sequence by deleting some elements (possibly none) without changing the order of the remaining elements.

Example

Input: arrays = [[1,3,4],
Output: [1,4]
Explanation: The longest common subsequence in the two arrays is [1,4].

Python solution

Python

class Solution:
    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
        cnt = [0] * 101
        for row in arrays:
            for x in row:
                cnt[x] += 1
        return [x for x, v in enumerate(cnt) if v == len(arrays)]

Complexity

Measure	Complexity
Time	O(M + N)
Space	O(M) auxiliary

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1940. Longest Common Subsequence Between Sorted Arrays is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1940. Longest Common Subsequence Between Sorted Arrays?: LeetCode 1940. Longest Common Subsequence Between Sorted Arrays is rated Medium on LeetCode.
What is the time complexity of LeetCode 1940. Longest Common Subsequence Between Sorted Arrays?: The Python solution on this page runs in O(M + N).
What is the space complexity of LeetCode 1940. Longest Common Subsequence Between Sorted Arrays?: The Python solution on this page uses O(M) auxiliary space.
What topics does LeetCode 1940. Longest Common Subsequence Between Sorted Arrays cover?: LeetCode 1940. Longest Common Subsequence Between Sorted Arrays is tagged Array, Hash Table and Counting on LeetCode.
Is LeetCode 1940. Longest Common Subsequence Between Sorted Arrays a premium problem?: Yes. LeetCode 1940. Longest Common Subsequence Between Sorted Arrays is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.