LeetCode 1940 - Longest Common Subsequence Between Sorted Arrays

The problem asks us to find the longest common subsequence (LCS) among multiple sorted integer arrays. In simpler terms, we are given a list of arrays where each array is sorted in strictly increasing order, and we need to identify the sequence of numbers that appears in all…

leetcodemediumarrayhash-tablecounting

LeetCode Problem 1940

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Counting

Solution

Problem Understanding

The problem asks us to find the longest common subsequence (LCS) among multiple sorted integer arrays. In simpler terms, we are given a list of arrays where each array is sorted in strictly increasing order, and we need to identify the sequence of numbers that appears in all arrays in the same relative order and is as long as possible. The result should also be returned as an array.

The input arrays is a list of integer arrays. Each arrays[i] is sorted strictly increasing, which means no duplicates exist in a single array. The expected output is an array containing the longest sequence that is a subsequence of every array in arrays. If no common elements exist, the output is an empty array.

Key constraints help guide our solution:

  • There are at most 100 arrays, each with up to 100 elements.
  • Every integer is in the range [1, 100].
  • Each array is strictly increasing.

These constraints suggest that the input sizes are moderate and bounded by small integers. The strictly increasing property hints that we can efficiently track common elements without worrying about duplicates in a single array.

Important edge cases include:

  • Arrays with no common elements, which should return an empty list.
  • Arrays where one array is much shorter than the others, potentially limiting the LCS length.
  • All arrays being identical, which should return the array itself.

Approaches

Brute Force

A naive approach would consider generating all possible subsequences of the first array and then check each against all other arrays to see if it appears as a subsequence. While correct in principle, this is prohibitively slow because the number of subsequences grows exponentially. For an array of length n, there are 2^n possible subsequences. With multiple arrays, this quickly becomes computationally infeasible.

Optimal Approach

The key insight comes from the constraints: all numbers are between 1 and 100, and arrays are sorted strictly increasing. This allows us to count occurrences across all arrays instead of checking every subsequence explicitly. If we iterate through the arrays and keep track of numbers that appear in all arrays, the common elements in sorted order automatically form a valid subsequence.

To implement this, we can:

  1. Create a hash map or counter to track how many arrays contain each number.
  2. Iterate through each array and update the counter, ensuring we only count each number once per array.
  3. After processing all arrays, extract numbers that appear in all arrays, preserving their order from the first array.

This approach guarantees the longest subsequence because the arrays are sorted, so the intersection of numbers in all arrays naturally maintains relative order.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * k) O(n) Generate all subsequences of the first array and check each in k arrays
Optimal O(k * m) O(100) Count common elements using a hash map and extract numbers appearing in all arrays

Here, k is the number of arrays and m is the maximum length of any array. The space complexity is small because numbers are bounded from 1 to 100.

Algorithm Walkthrough

  1. Initialize a dictionary count to store the number of arrays in which each number appears.
  2. Iterate through each array. For each array, create a temporary set of its elements to avoid counting duplicates within the same array.
  3. Update count for each number in the temporary set.
  4. Initialize an empty list result to store the longest common subsequence.
  5. Iterate through the first array. For each number, check if count[number] equals the total number of arrays. If so, append it to result.
  6. Return result.

Why it works: The algorithm works because we only include numbers that appear in every array, and iterating through the first array ensures the relative order of elements is preserved. Since arrays are strictly increasing, the order in the first array reflects the correct subsequence order.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def longestCommonSubsequence(self, arrays: List[List[int]]) -> List[int]:
        count = defaultdict(int)
        total_arrays = len(arrays)
        
        for arr in arrays:
            seen = set()
            for num in arr:
                if num not in seen:
                    count[num] += 1
                    seen.add(num)
        
        result = []
        for num in arrays[0]:
            if count[num] == total_arrays:
                result.append(num)
        
        return result

Explanation:

The code initializes a count dictionary to record the number of arrays each number appears in. For each array, a seen set ensures that duplicates in the same array do not inflate the count. After counting, we iterate through the first array to maintain the correct order, adding numbers that appear in all arrays to the result.

Go Solution

func longestCommonSubsequence(arrays [][]int) []int {
    count := make(map[int]int)
    totalArrays := len(arrays)
    
    for _, arr := range arrays {
        seen := make(map[int]bool)
        for _, num := range arr {
            if !seen[num] {
                count[num]++
                seen[num] = true
            }
        }
    }
    
    result := []int{}
    for _, num := range arrays[0] {
        if count[num] == totalArrays {
            result = append(result, num)
        }
    }
    
    return result
}

Go notes: We use map[int]int for counting occurrences and map[int]bool to track numbers already seen in the current array. The slice result collects numbers in the order of the first array, ensuring correct subsequence order.

Worked Examples

Example 1: arrays = [[1,3,4],[1,4,7,9]]

Step Array Count Dict Result
1 [1,3,4] {1:1, 3:1, 4:1} []
2 [1,4,7,9] {1:2, 3:1, 4:2, 7:1, 9:1} []
3 first array iteration - [1,4]

Example 2: arrays = [[2,3,6,8],[1,2,3,5,6,7,10],[2,3,4,6,9]]

Step Array Count Dict Result
1 [2,3,6,8] {2:1,3:1,6:1,8:1} []
2 [1,2,3,5,6,7,10] {1:1,2:2,3:2,5:1,6:2,7:1,8:1,10:1} []
3 [2,3,4,6,9] {1:1,2:3,3:3,4:1,5:1,6:3,7:1,8:1,9:1,10:1} []
4 first array iteration - [2,3,6]

Example 3: arrays = [[1,2,3,4,5],[6,7,8]]

Step Array Count Dict Result
1 [1,2,3,4,5] {1:1,2:1,3:1,4:1,5:1} []
2 [6,7,8] {1:1,2:1,3:1,4:1,5:1,6:1,7:1,8:1} []
3 first array iteration - []

Complexity Analysis

Measure Complexity Explanation
Time O(k * m) Each array is processed once, counting elements; first array is iterated for result
Space O(100) Maximum of 100 unique integers stored in the count dictionary

The time complexity is efficient because the maximum array size and number values are small. The space complexity is bounded by the number range rather than array lengths.

Test Cases

# provided examples
assert Solution().longestCommonSubsequence([[1,3,4],[1,4,7,9]]) == [1,4]  # Example 1
assert Solution().longestCommonSubsequence([[2,3,6,8],[1,2,3,5,6,7,10],[2,3,4,6,9]]) == [2,3,6]  # Example 2
assert Solution().longestCommonSubsequence([[1,2,3,4,5],[6,7,8]]) == []  # Example 3

# edge cases
assert Solution().longestCommonSubsequence([[1,2,3]]) == [1,2,3]  # Single array
assert Solution().longestCommonSubsequence([[1,2],[2,3],[2,4]]) == [2