1940. Longest Common Subsequence Between Sorted Arrays

MediumArrayHash TableCounting
Leetcode Link

Problem Description

The problem provides an array of integer arrays, where each inner array is already sorted in strictly increasing order. The task is to find the longest common subsequence present in all these arrays.

A subsequence is a sequence that can be obtained from another sequence by deleting zero or more elements without changing the order of the remaining elements. Since we are interested in the common subsequence among all the arrays, our goal is to identify numbers that are present in every single array provided.

The output should be an integer array listing the elements of the longest common subsequence in any order.

Intuition

The intuition behind the solution centers on frequency analysis of each element across all the arrays. Since all the arrays are sorted in strictly increasing order, each number will be present at most once in every array. To find common elements, we need to count the occurrences of each number and check if the count matches the number of arrays. If a particular number appears as many times as there are arrays, we can conclude that this number is a part of the common subsequence for all arrays.

Here is the thought process for arriving at the solution:

  1. Create a frequency map that holds the count of each element across all arrays.
  2. Iterate over each array and for each element, increase its count in the map by one.
  3. After processing all arrays, iterate through the map entries to check which elements have a count equal to the total number of arrays.
  4. If an element's count equals the number of arrays, it is a common element and thus a part of the longest common subsequence.
  5. Collect these common elements into a result list and return it.

This approach is efficient because it minimizes the need for nested iterations over all elements of all arrays. Instead, it allows us to make the decision after a single pass through all arrays and a single pass through the frequency map.

Solution Approach

The implementation of the solution uses the following steps and components:

  1. HashMap for Frequency Counting: A HashMap<Integer, Integer> named counter is used to keep track of the frequency of each integer. The keys in the map are the integers from the arrays, and the values are the counts representing how many arrays that integer appears in.

  2. Iterate Over Arrays: The first for loop iterates over the given array of arrays. Each inner array is accessed in sequence.

  3. Increment Counts: The nested for loop iterates over each integer in the current inner array. For every integer e, the code uses the counter map to increment the count associated with e. If the element is not already in the map, it is added with a default count of 0 using getOrDefault() before being incremented.

    1for (int e : array) {
    2    counter.put(e, counter.getOrDefault(e, 0) + 1);
    3}
  4. Check for Common Integers:

    • The variable n holds the number of arrays, which is essential to determine if an integer is common to all arrays.
    • After counting the occurrences, the code iterates over the entries in the counter map.
  5. Collect Common Integers: If an entry in counter has a value equal to n (number of arrays), it means the key (integer) is present in all arrays. Such keys are added to the res list.

    1for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
    2    if (entry.getValue() == n) {
    3        res.add(entry.getKey());
    4    }
    5}
  6. Return the Result: Finally, the list res is returned, which contains all the integers that form the longest common subsequence between all arrays.

This approach harnesses the efficiency of hash maps to quickly access and update counts, avoiding quadratic runtime complexity that might arise from comparing each element of every array with each other. By leveraging the uniqueness of elements within each sorted array and the simple condition that an element must appear in each array exactly once to be included in the common subsequence, this algorithm achieves the desired results in an optimal manner.

Example Walkthrough

Consider the following three arrays representing the input, with each inner array sorted in strictly increasing order:

1array1: [1, 3, 4]
2array2: [1, 2, 3, 4, 5]
3array3: [1, 3, 5, 7, 9]

The goal is to find the longest common subsequence among these arrays. Following the solution approach:

  1. HashMap for Frequency Counting: We initialize an empty HashMap<Integer, Integer> named counter.

  2. Iterate Over Arrays: We start by iterating over each given array. We will process array1, array2, and array3 in turn.

  3. Increment Counts:

    • When we process array1, the counter map will be updated as follows: counter = {1:1, 3:1, 4:1}
    • Next, processing array2 updates the map to: counter = {1:2, 2:1, 3:2, 4:2, 5:1}
    • Finally, processing array3 yields: counter = {1:3, 2:1, 3:3, 4:2, 5:2, 7:1, 9:1}
  4. Check for Common Integers: The n variable holds the number of arrays, which in this case is 3. We check each entry in the counter map to see if it has a value equal to 3.

  5. Collect Common Integers: As we iterate through the map:

    • The integer 1 has a count of 3, so it is added to the res list.
    • The integer 3 has a count of 3, so it is also added to the res list.
    • No other integers meet the condition of being present in all arrays.
  6. Return the Result: We return the list res, which now contains [1, 3]. These are the integers present in all the provided arrays, forming the longest common subsequence. The order of elements in the result is irrelevant.

Therefore, by following this approach, we efficiently find [1, 3] as the longest common subsequence between the given arrays using a HashMap to account for the frequency and simple iteration techniques.

Python Solution

1def longest_common_subsequence(arrays):
2    """
3    Finds the longest common subsequence present in each of the sub-arrays
4    of the provided 2D array.
5    :param arrays: A 2D list where each sub-list is to be checked for common elements.
6    :return: A list containing the longest common subsequence found in all sub-arrays.
7    """
8    # Initialize a dictionary to keep track of the frequency of each element across all sub-arrays.
9    element_count_map = {}
10  
11    # Initialize a list to store the result (longest common subsequence).
12    result_sequence = []
13  
14    # total_arrays represents the total number of sub-arrays in the given 2D list.
15    total_arrays = len(arrays)
16  
17    # Initially assume that all elements are possible candidates for the LCS (Longest Common Subsequence).
18    potential_lcs = set(arrays[0])
19  
20    # Iterate over each sub-array.
21    for sub_array in arrays:
22        # Update potential_lcs by intersecting with the set of elements in the current sub-array.
23        # This keeps only those elements that are candidates for LCS from all sub-arrays seen so far.
24        potential_lcs &= set(sub_array)
25  
26    # Go through each element in the potential LCS set.
27    for element in potential_lcs:
28        # Count how many times the element appears in each sub-array and compare against the total.
29        count = sum(element in sub for sub in arrays)
30      
31        # If the count is equal to the total number of sub-arrays, add it to the result.
32        if count == total_arrays:
33            result_sequence.append(element)
34  
35    # Return the list containing the longest common subsequence across all sub-arrays.
36    return result_sequence
37

Java Solution

1import java.util.List;
2import java.util.ArrayList;
3import java.util.Map;
4import java.util.HashMap;
5
6class Solution {
7    // Finds the common elements that appear in all the subarrays
8    public List<Integer> longestCommonSubsequence(int[][] arrays) {
9        // Using a map to count occurrences of each integer in all arrays
10        Map<Integer, Integer> frequencyCounter = new HashMap<>();
11      
12        // Iterate through all the arrays
13        for (int[] array : arrays) {
14            // Iterate through each element of the current array
15            for (int element : array) {
16                // Increment the count for the element in the map
17                frequencyCounter.put(element, frequencyCounter.getOrDefault(element, 0) + 1);
18            }
19        }
20      
21        // The length of the arrays or number of arrays
22        int numberOfArrays = arrays.length;
23      
24        // List to store the common elements found in all the arrays
25        List<Integer> result = new ArrayList<>();
26      
27        // Iterate through the map entries
28        for (Map.Entry<Integer, Integer> entry : frequencyCounter.entrySet()) {
29            // If the count of the element is equal to the number of arrays
30            // then add it to the result list as it appears in all arrays
31            if (entry.getValue() == numberOfArrays) {
32                result.add(entry.getKey());
33            }
34        }
35      
36        // Return the list of common elements
37        return result;
38    }
39}
40

C++ Solution

1#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6    // Function to find the longest common subsequence among all arrays.
7    std::vector<int> longestCommomSubsequence(std::vector<std::vector<int>>& arrays) {
8        // This map will count the frequency of each element across all arrays.
9        std::unordered_map<int, int> elementFrequency;
10        // This vector will store the results - the longest common subsequence
11        std::vector<int> result;
12        // Total number of arrays
13        int numberOfArrays = arrays.size();
14      
15        // Iterate through each array in the collection of arrays
16        for (auto &array : arrays) {
17            // Using a std::unordered_set to ensure each element in the same array is counted once
18            std::unordered_set<int> uniqueElements;
19          
20            // Iterate through each element of the current array
21            for (int element : array) {
22                // If this is the first occurrence of this element in this array
23                if (uniqueElements.insert(element).second) {
24                    // Increment the counter for this element by one
25                    elementFrequency[element]++;
26                  
27                    // If the current element's count matches the number of arrays
28                    // it means this element is present in all arrays
29                    if (elementFrequency[element] == numberOfArrays) {
30                        // Add the element to the result vector
31                        result.push_back(element);
32                    }
33                }
34            }
35        }
36      
37        // Before returning, ensure that the results vector is sorted
38        // Since the order in the result does not matter by the prompt,
39        // but a sorted array might be a common expectation.
40        std::sort(result.begin(), result.end());
41
42        // Return the final vector containing the longest common subsequence
43        return result;
44    }
45};
46

Typescript Solution

1/**
2 * Finds the longest common subsequence present in each of the sub-arrays of the provided 2D array.
3 * @param {number[][]} arrays - A 2D array where each sub-array is to be checked for common elements.
4 * @return {number[]} - An array containing the longest common subsequence found in all sub-arrays.
5 */
6function longestCommonSubsequence(arrays: number[][]): number[] {
7    // Initialize a map to keep track of the frequency of each element across all sub-arrays.
8    const elementCountMap = new Map<number, number>();
9  
10    // Initialize an array to store the result (longest common subsequence).
11    const resultSequence: number[] = [];
12  
13    // totalArrays represents the total number of sub-arrays in the given 2D array.
14    const totalArrays: number = arrays.length;
15  
16    // Iterate over each sub-array.
17    for (let i = 0; i < totalArrays; i++) {
18        // Iterate over each element in the sub-array.
19        for (let j = 0; j < arrays[i].length; j++) {
20            // Get the current element.
21            const element = arrays[i][j];
22          
23            // Update the frequency count of the current element in the map.
24            elementCountMap.set(element, (elementCountMap.get(element) || 0) + 1);
25          
26            // If the current element's frequency matches the total number of sub-arrays,
27            // include it in the resultSequence as it's common in all sub-arrays.
28            if (elementCountMap.get(element) === totalArrays) {
29                resultSequence.push(element);
30            }
31        }
32    }
33  
34    // Return the array that contains the longest common subsequence across all sub-arrays.
35    return resultSequence;
36}
37

Time and Space Complexity

Time Complexity

The time complexity of the code mainly consists of two parts:

  1. The first loop, which iterates over each array in arrays and then over each element e in these arrays, resulting in a time complexity of O(N * M), where N is the number of arrays, and M is the average length of each array.
  2. The second loop, which iterates over entries in the counter hashmap. The size of the hashmap is at most equal to the number of unique elements across all arrays. Let's denote this as U. This results in O(U) time complexity for the second loop.

Overall, assuming U <= N * M, the time complexity is O(N * M), as this is the dominating factor.

Space Complexity

The space complexity is determined by the space required to store the counter hashmap, which holds as many as U unique elements and their counts across all arrays. Thus, the space complexity is O(U). In the worst case where all elements are unique across all arrays, U would be equal to N * M, leading to a worst-case space complexity of O(N * M).

Additionally, space is used for the resultant res ArrayList, but since the size of res is at most U, it does not exceed the space complexity determined by counter.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫