Problem Description

You are given an array of integer arrays called arrays, where each individual array arrays[i] is sorted in strictly increasing order (no duplicates within each array).

Your task is to find the longest common subsequence that appears in all the arrays and return it as an integer array.

A subsequence is a sequence that can be obtained from another sequence by removing some elements (or none) while maintaining the relative order of the remaining elements. For example, [1, 3, 5] is a subsequence of [1, 2, 3, 4, 5].

The key points to understand:

• Each array in arrays contains unique elements in strictly increasing order
• You need to find elements that appear in every single array
• The result should preserve the order of elements as they would appear in any subsequence
• Since all arrays are sorted and contain unique elements, the common subsequence will also be sorted

For example, if arrays = [[1,3,4], [1,4,7,9]], the longest common subsequence would be [1,4] because both 1 and 4 appear in both arrays.

The solution leverages the fact that:

• Elements have a limited range [1, 100]
• Since each array has unique elements in increasing order, we can simply count how many arrays contain each element
• Elements that appear in all arrays (count equals the number of arrays) form the common subsequence
• Due to the sorted nature of the input arrays, collecting these common elements in order automatically gives us the longest common subsequence

Intuition

The key insight comes from understanding what makes this problem simpler than it initially appears. At first glance, finding the longest common subsequence might seem complex, but there are several properties we can exploit:

First, notice that each individual array contains unique elements in strictly increasing order. This means no element appears twice in the same array. So if an element appears in an array, it appears exactly once.

Second, for an element to be part of the common subsequence, it must appear in every single array. Since each element can appear at most once per array, we can simply count how many arrays contain each element. If an element appears in all n arrays, it must be part of the common subsequence.

Third, the constraint that elements are in the range [1, 100] is crucial. This small range allows us to use a simple counting array instead of more complex data structures. We can create an array cnt of size 101 where cnt[x] tracks how many arrays contain the element x.

Finally, here's the beautiful part: since all input arrays are sorted in increasing order, and we're looking for elements that appear in all arrays, when we collect these common elements in ascending order (by iterating through our counting array from index 1 to 100), we automatically get the longest common subsequence in the correct order!

The algorithm becomes surprisingly simple:

1. Count occurrences of each element across all arrays
2. Collect elements whose count equals the total number of arrays
3. Since we iterate through counts in ascending order, the result is automatically sorted

This transforms what could be a complex dynamic programming problem into a simple counting problem with O(n*m) time complexity, where n is the number of arrays and m is the average length of each array.

Solution Approach

The implementation uses a counting strategy to efficiently find the longest common subsequence:

Step 1: Initialize the Counting Array

We create an array cnt of size 101 to track occurrences of each element. Since elements range from [1, 100], we use index positions directly to represent the elements:

cnt = [0] * 101

Step 2: Count Element Occurrences

We iterate through each array in arrays and for each element in these arrays, increment its count:

for row in arrays:
    for x in row:
        cnt[x] += 1

This nested loop processes every element exactly once. If an element x appears in k different arrays, then cnt[x] will equal k.

Step 3: Identify Common Elements

We need to find elements that appear in all arrays. An element is part of the common subsequence if and only if its count equals the total number of arrays:

return [x for x, v in enumerate(cnt) if v == len(arrays)]

This list comprehension:

• Iterates through the counting array using enumerate(cnt) to get both index x (the element value) and count v
• Filters elements where v == len(arrays) (appears in all arrays)
• Collects these elements into the result list

Why This Works:

1. Correctness: Since each array has unique elements in strictly increasing order, an element appearing in all arrays guarantees it's part of the common subsequence.

2. Order Preservation: By iterating through cnt from index 0 to 100, we naturally process elements in ascending order. This ensures the output is sorted, which matches the subsequence order requirement.

3. Time Complexity: O(n * m + k) where n is the number of arrays, m is the average array length, and k is the range of elements (100). Since k is constant, this simplifies to O(n * m).

4. Space Complexity: O(1) extra space, as the counting array has a fixed size of 101 regardless of input size.

The elegance of this solution lies in transforming a potentially complex subsequence problem into a simple counting problem by leveraging the constraints of sorted arrays with unique elements.

Example Walkthrough

Let's walk through the solution with a concrete example to see how the counting approach works.

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

Step 1: Initialize the counting array We create cnt = [0] * 101 to track occurrences of elements from 1 to 100.

Step 2: Process each array and count elements

Processing first array [2,3,6,8]:

• cnt[2] becomes 1
• cnt[3] becomes 1
• cnt[6] becomes 1
• cnt[8] becomes 1

Processing second array [1,2,3,5,6]:

• cnt[1] becomes 1
• cnt[2] becomes 2 (was 1, now 2)
• cnt[3] becomes 2 (was 1, now 2)
• cnt[5] becomes 1
• cnt[6] becomes 2 (was 1, now 2)

Processing third array [2,3,4,6,9]:

• cnt[2] becomes 3 (was 2, now 3)
• cnt[3] becomes 3 (was 2, now 3)
• cnt[4] becomes 1
• cnt[6] becomes 3 (was 2, now 3)
• cnt[9] becomes 1

Step 3: Identify common elements We have 3 arrays total, so we look for elements where cnt[x] == 3:

• cnt[1] = 1 ❌ (only in 1 array)
• cnt[2] = 3 ✅ (in all 3 arrays)
• cnt[3] = 3 ✅ (in all 3 arrays)
• cnt[4] = 1 ❌ (only in 1 array)
• cnt[5] = 1 ❌ (only in 1 array)
• cnt[6] = 3 ✅ (in all 3 arrays)
• cnt[8] = 1 ❌ (only in 1 array)
• cnt[9] = 1 ❌ (only in 1 array)

Step 4: Build the result Collecting elements where count equals 3: [2, 3, 6]

This is indeed the longest common subsequence! We can verify:

• In array 1: [2,3,6,8] contains subsequence [2,3,6] ✓
• In array 2: [1,2,3,5,6] contains subsequence [2,3,6] ✓
• In array 3: [2,3,4,6,9] contains subsequence [2,3,6] ✓

The beauty of this approach is that we don't need to worry about maintaining order - since we iterate through the counting array from low to high indices, and all original arrays are sorted, the result naturally comes out in the correct sorted order.

Solution Implementation

Time and Space Complexity

The time complexity is O(N + M), where N is the total number of elements across all arrays and M is the range of possible elements (in this case, M = 101). Breaking this down:

• The nested loops iterate through every element in all arrays exactly once, contributing O(N) time
• The final list comprehension iterates through the count array of size M, contributing O(M) time
• Combined: O(N + M)

The space complexity is O(M), where M = 101 is the size of the count array. The cnt array has a fixed size of 101 regardless of the input size, and the output list in the worst case could contain all elements from 0 to 100, but this is still bounded by O(M).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Problem - Confusing with Traditional LCS

The Mistake: Many developers initially approach this problem thinking it requires the traditional Longest Common Subsequence (LCS) dynamic programming algorithm. They might attempt to implement a complex DP solution that finds the actual longest subsequence between arrays, preserving relative order within each array.

Why It Happens: The problem title "longest common subsequence" triggers pattern recognition for the classic LCS problem. Developers might write code like:

# INCORRECT approach - treating it as traditional LCS
def longestCommonSubsequence(self, arrays):
    if not arrays:
        return []
  
    result = arrays[0]
    for i in range(1, len(arrays)):
        result = self.findLCS(result, arrays[i])  # Complex DP logic
    return result

The Reality: This problem is actually asking for elements that appear in ALL arrays, not a traditional subsequence. Since each array contains unique elements in strictly increasing order, any common elements automatically form a valid subsequence.

Correct Understanding:

• We need elements present in EVERY array
• The order is automatically preserved due to sorted inputs
• It's a set intersection problem, not a DP subsequence problem

Pitfall 2: Off-by-One Error with Array Indexing

The Mistake: Using incorrect array bounds or forgetting that array indices start at 0:

# INCORRECT - using wrong array size
frequency_count = [0] * 100  # Missing index 100

# OR INCORRECT - wrong iteration
for value in range(1, 101):  # Skips index 0
    if frequency_count[value] == len(arrays):
        result.append(value)

The Fix: Always allocate 101 elements (indices 0-100) and use enumerate to safely iterate:

frequency_count = [0] * 101  # Covers indices 0-100

# Use enumerate for safe iteration
for value, count in enumerate(frequency_count):
    if count == len(arrays):
        result.append(value)

Pitfall 3: Handling Edge Cases Incorrectly

The Mistake: Not considering edge cases like empty input or single array:

# INCORRECT - might fail on edge cases
def longestCommonSubsequence(self, arrays):
    frequency_count = [0] * 101
    for array in arrays:
        for number in array:
            frequency_count[number] += 1
  
    # What if arrays is empty? len(arrays) would be 0
    # This would return ALL elements with count 0
    return [x for x, v in enumerate(frequency_count) if v == len(arrays)]

The Fix: Add edge case handling:

def longestCommonSubsequence(self, arrays):
    if not arrays:
        return []
  
    if len(arrays) == 1:
        return arrays[0]  # Single array case
  
    frequency_count = [0] * 101
    # ... rest of the solution

Pitfall 4: Assuming Elements Can Repeat Within an Array

The Mistake: Writing defensive code to handle duplicate elements within a single array:

# UNNECESSARY complexity
seen_in_current = set()
for array in arrays:
    for number in array:
        if number not in seen_in_current:
            frequency_count[number] += 1
            seen_in_current.add(number)
    seen_in_current.clear()

Why It's Wrong: The problem explicitly states each array contains unique elements in strictly increasing order. Adding duplicate-handling logic:

• Increases complexity unnecessarily
• Makes the code harder to read
• Adds potential for bugs

The Correct Approach: Trust the problem constraints and keep the solution simple:

for array in arrays:
    for number in array:
        frequency_count[number] += 1  # Simple and correct