Problem

Given an array of integer arrays arrays where each arrays[i] is sorted in strictly increasing order, return an integer array representing thelongest 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.

Examples

Example 1:

1
2
3
4

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:

1
2
3
4
5

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:

1
2
3
4

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.

Solution

Method 1 – Hash Map Counting (1)

Intuition

Since each array is strictly increasing and sorted, we can count the frequency of each number across all arrays. The numbers that appear in all arrays (frequency equals the number of arrays) form the longest common subsequence.

Approach

  1. Initialize a hash map to count occurrences of each number across all arrays.
  2. For each array, iterate through its elements and increment their count in the map.
  3. After processing all arrays, collect numbers whose count equals the number of arrays.
  4. Return the sorted list of these numbers as the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    vector<int> longestCommonSubsequence(vector<vector<int>>& arrays) {
        unordered_map<int, int> cnt;
        int n = arrays.size();
        for (auto& arr : arrays)
            for (int x : arr)
                cnt[x]++;
        vector<int> ans;
        for (auto& [k, v] : cnt)
            if (v == n) ans.push_back(k);
        sort(ans.begin(), ans.end());
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func longestCommonSubsequence(arrays [][]int) []int {
    cnt := map[int]int{}
    n := len(arrays)
    for _, arr := range arrays {
        for _, x := range arr {
            cnt[x]++
        }
    }
    ans := []int{}
    for k, v := range cnt {
        if v == n {
            ans = append(ans, k)
        }
    }
    sort.Ints(ans)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public List<Integer> longestCommonSubsequence(List<List<Integer>> arrays) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = arrays.size();
        for (List<Integer> arr : arrays)
            for (int x : arr)
                cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        List<Integer> ans = new ArrayList<>();
        for (int k : cnt.keySet())
            if (cnt.get(k) == n) ans.add(k);
        Collections.sort(ans);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun longestCommonSubsequence(arrays: List<List<Int>>): List<Int> {
        val cnt = mutableMapOf<Int, Int>()
        val n = arrays.size
        for (arr in arrays)
            for (x in arr)
                cnt[x] = cnt.getOrDefault(x, 0) + 1
        val ans = cnt.filter { it.value == n }.keys.sorted()
        return ans
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def longestCommonSubsequence(self, arrays: list[list[int]]) -> list[int]:
        from collections import Counter
        n = len(arrays)
        cnt = Counter()
        for arr in arrays:
            cnt.update(arr)
        return sorted([k for k, v in cnt.items() if v == n])
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn longest_common_subsequence(arrays: Vec<Vec<i32>>) -> Vec<i32> {
        use std::collections::HashMap;
        let n = arrays.len();
        let mut cnt = HashMap::new();
        for arr in arrays.iter() {
            for &x in arr.iter() {
                *cnt.entry(x).or_insert(0) += 1;
            }
        }
        let mut ans: Vec<i32> = cnt.iter().filter(|&(_, &v)| v == n).map(|(&k, _)| k).collect();
        ans.sort();
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    longestCommonSubsequence(arrays: number[][]): number[] {
        const cnt = new Map<number, number>();
        const n = arrays.length;
        for (const arr of arrays) {
            for (const x of arr) {
                cnt.set(x, (cnt.get(x) || 0) + 1);
            }
        }
        const ans = [];
        for (const [k, v] of cnt.entries()) {
            if (v === n) ans.push(k);
        }
        ans.sort((a, b) => a - b);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(NL + M log M), where N is the number of arrays, L is the average length, and M is the number of unique elements. We count and then sort the result.
  • 🧺 Space complexity: O(M), for the hash map and result.