Skip to content

Latest commit

 

History

History
208 lines (168 loc) · 5.65 KB

README_EN.md

File metadata and controls

208 lines (168 loc) · 5.65 KB
comments difficulty edit_url tags
true
Medium
Array
Hash Table
Counting

1940. Longest Common Subsequence Between Sorted Arrays 🔒

中文文档

Description

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 1:

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

Example 2:

Input: arrays = [[2,3,6,8],
                 [1,2,3,5,6,7,10],
                 [2,3,4,6,9]]
Output: [2,3,6]
Explanation: The longest common subsequence in all three arrays is [2,3,6].

Example 3:

Input: arrays = [[1,2,3,4,5],
                 [6,7,8]]
Output: []
Explanation: There is no common subsequence between the two arrays.

 

Constraints:

  • 2 <= arrays.length <= 100
  • 1 <= arrays[i].length <= 100
  • 1 <= arrays[i][j] <= 100
  • arrays[i] is sorted in strictly increasing order.

Solutions

Solution 1: Counting

We note that the range of elements is $[1, 100]$, so we can use an array $\textit{cnt}$ of length $101$ to record the number of occurrences of each element.

Since each array in $\textit{arrays}$ is strictly increasing, the elements of the common subsequence must be monotonically increasing, and the number of occurrences of these elements must be equal to the length of $\textit{arrays}$.

Therefore, we can traverse each array in $\textit{arrays}$ and count the number of occurrences of each element. Finally, traverse each element of $\textit{cnt}$ from smallest to largest. If the number of occurrences is equal to the length of $\textit{arrays}$, then this element is one of the elements of the common subsequence, and we add it to the answer array.

After the traversal, return the answer array.

The time complexity is $O(M + N)$, and the space complexity is $O(M)$. Here, $M$ is the range of elements, and in this problem, $M = 101$, and $N$ is the total number of elements in the arrays.

Python3

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)]

Java

class Solution {
    public List<Integer> longestCommonSubsequence(int[][] arrays) {
        int[] cnt = new int[101];
        for (var row : arrays) {
            for (int x : row) {
                ++cnt[x];
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < 101; ++i) {
            if (cnt[i] == arrays.length) {
                ans.add(i);
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> longestCommonSubsequence(vector<vector<int>>& arrays) {
        int cnt[101]{};
        for (const auto& row : arrays) {
            for (int x : row) {
                ++cnt[x];
            }
        }
        vector<int> ans;
        for (int i = 0; i < 101; ++i) {
            if (cnt[i] == arrays.size()) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

Go

func longestCommonSubsequence(arrays [][]int) (ans []int) {
	cnt := [101]int{}
	for _, row := range arrays {
		for _, x := range row {
			cnt[x]++
		}
	}
	for x, v := range cnt {
		if v == len(arrays) {
			ans = append(ans, x)
		}
	}
	return
}

TypeScript

function longestCommonSubsequence(arrays: number[][]): number[] {
    const cnt: number[] = Array(101).fill(0);
    for (const row of arrays) {
        for (const x of row) {
            ++cnt[x];
        }
    }
    const ans: number[] = [];
    for (let i = 0; i < 101; ++i) {
        if (cnt[i] === arrays.length) {
            ans.push(i);
        }
    }
    return ans;
}

JavaScript

/**
 * @param {number[][]} arrays
 * @return {number[]}
 */
var longestCommonSubsequence = function (arrays) {
    const cnt = Array(101).fill(0);
    for (const row of arrays) {
        for (const x of row) {
            ++cnt[x];
        }
    }
    const ans = [];
    for (let i = 0; i < 101; ++i) {
        if (cnt[i] === arrays.length) {
            ans.push(i);
        }
    }
    return ans;
};