{x}
blog image

Longest Common Subsequence Between Sorted Arrays

Solution Explanation: Longest Common Subsequence Between Sorted Arrays

This problem asks to find the longest common subsequence among multiple sorted arrays. The constraint that the arrays are sorted and the numbers are within a limited range (1-100) allows for an efficient counting-based solution.

Approach:

The core idea is to leverage the fact that the input arrays are sorted and the numbers are within a small range (1 to 100). We can use a counting array to track the frequency of each number across all input arrays. Any number that appears in all arrays is part of the longest common subsequence.

  1. Counting Frequencies: We create a frequency array cnt of size 101 (to accommodate numbers from 0 to 100). We iterate through each input array and increment the count for each number encountered in cnt.

  2. Identifying Common Elements: After counting frequencies, we iterate through the cnt array. If a number's frequency is equal to the number of input arrays (arrays.length), it means that number is present in all arrays. We add such numbers to the result array ans.

  3. Return Result: The ans array, containing the numbers that are common to all input arrays, represents the longest common subsequence.

Time and Space Complexity Analysis:

  • Time Complexity: O(M + N), where M is the range of numbers (101 in this case) and N is the total number of elements across all input arrays. The counting step takes O(N) time, and iterating through the cnt array takes O(M) time.

  • Space Complexity: O(M), as we use a counting array cnt of size M to store frequencies.

Code Examples:

The code examples below demonstrate the solution in various programming languages. They all follow the same algorithmic approach described above.

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

Java:

class Solution {
    public List<Integer> longestCommonSubsequence(int[][] arrays) {
        int[] cnt = new int[101];
        for (int[] 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
}

JavaScript:

var longestCommonSubsequence = function(arrays) {
    const cnt = new 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;
};

TypeScript:

function longestCommonSubsequence(arrays: number[][]): number[] {
    const cnt: number[] = new 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;
}

These codes are all highly efficient due to the use of the counting array and direct access to elements based on their value. They avoid the need for nested loops or more complex dynamic programming techniques which would be necessary if the input arrays were unsorted or the range of numbers were much larger.