Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1940.html

1940. Longest Common Subsequence Between Sorted Arrays

Level

Medium

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 between 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.

Solution

Any element in the longest common subsequence must be in all of the arrays. Since all arrays are sorted in strictly increasing order, the same element does not exist more than once in the same array. Loop over all arrays and use a hash map to store each number’s number of occurrences in all arrays.

Then loop over the shortest array among all arrays, and obtain the elements that have numbers of occurrences equal to the number of arrays. These elements form the longest common subsequence.

  • class Solution {
    public List<Integer> longestCommomSubsequence(int[][] arrays) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        int count = arrays.length;
        int shortestIndex = 0, shortestLength = arrays[0].length;
        for (int i = 0; i < count; i++) {
            int[] array = arrays[i];
            if (array.length < shortestLength) {
                shortestIndex = i;
                shortestLength = array.length;
            }
            for (int num : array)
                map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer> subsequence = new ArrayList<Integer>();
        int[] shortestArray = arrays[shortestIndex];
        for (int i = 0; i < shortestLength; i++) {
            int num = shortestArray[i];
            if (map.get(num) == count)
                subsequence.add(num);
        }
        return subsequence;
    }
}

############

class Solution {
    public List<Integer> longestCommomSubsequence(int[][] arrays) {
        Map<Integer, Integer> counter = new HashMap<>();
        for (int[] array : arrays) {
            for (int e : array) {
                counter.put(e, counter.getOrDefault(e, 0) + 1);
            }
        }
        int n = arrays.length;
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
            if (entry.getValue() == n) {
                res.add(entry.getKey());
            }
        }
        return res;
    }
}

  • class Solution {
public:
    vector<int> longestCommomSubsequence(vector<vector<int>>& arrays) {
        unordered_map<int, int> counter;
        vector<int> res;
        int n = arrays.size();
        for (auto array : arrays) {
            for (auto e : array) {
                counter[e] += 1;
                if (counter[e] == n) {
                    res.push_back(e);
                }
            }
        }
        return res;
    }
};

  • func longestCommomSubsequence(arrays [][]int) []int {
    counter := make(map[int]int)
    n := len(arrays)
    var res []int
    for _, array := range arrays {
        for _, e := range array {
            counter[e]++
            if counter[e] == n {
                res = append(res, e)
            }
        }
    }
    return res
}

  • /**
 * @param {number[][]} arrays
 * @return {number[]}
 */
var longestCommonSubsequence = function (arrays) {
    const m = new Map();
    const rs = [];
    const len = arrays.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < arrays[i].length; j++) {
            m.set(arrays[i][j], (m.get(arrays[i][j]) || 0) + 1);
            if (m.get(arrays[i][j]) === len) rs.push(arrays[i][j]);
        }
    }
    return rs;
};

All Problems

All Solutions