Longest Common Subsequence Between Sorted Arrays

Longest Common Subsequence Between Sorted Arrays - Problem

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

The result should be sorted in strictly increasing order.

Input & Output

Example 1 — Basic Case

$ Input: arrays = [[1,2,3,4],[1,2,3],[1,2,4]]

› Output: [1,2]

💡 Note: Elements 1 and 2 appear in all three arrays. Element 3 appears in first two arrays only, element 4 appears in first and third arrays only.

Example 2 — Single Array

$ Input: arrays = [[1,2,3]]

› Output: [1,2,3]

💡 Note: With only one array, all elements [1,2,3] form the common subsequence.

Example 3 — No Common Elements

$ Input: arrays = [[1,2],[3,4]]

› Output: []

💡 Note: No elements appear in both arrays, so the longest common subsequence is empty.

Constraints

1 ≤ arrays.length ≤ 1000
1 ≤ arrays[i].length ≤ 1000
1 ≤ arrays[i][j] ≤ 10⁵
arrays[i] is sorted in strictly increasing order

Visualization

Tap to expand

Understanding the Visualization

Input

Multiple sorted arrays with some overlapping elements

Process

Find elements present in every single array

Output

Common elements in sorted order

Key Takeaway

🎯 Key Insight: Count frequency of each element - those appearing in exactly n arrays form the longest common subsequence

Asked in

G Google 25 a Amazon 20 f Facebook 15

The key insight is that an element belongs to the longest common subsequence if and only if it appears in every single array. The frequency counting approach efficiently tracks how many arrays each element appears in. Best approach uses hash map to count frequencies in O(n×m) time and O(k) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Each Element	O(n × m × k)	O(1)	For each element in first array, check if it exists in all other arrays
Frequency Counting	O(n × m)	O(k)	Count frequency of each element across all arrays

Brute Force - Check Each Element — Algorithm Steps

Take each element from the first array
Search for this element in every other array
If found in all arrays, add to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Take Element

Pick element from first array

Search All

Check if it exists in every other array

Add If Found

Add to result if found in all arrays

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int* solution(int** arrays, int* arraySizes, int arraysSize, int* returnSize) {
    *returnSize = 0;
    if (arraysSize == 0 || arraySizes[0] == 0) {
        return NULL;
    }
    
    int* result = (int*)malloc(arraySizes[0] * sizeof(int));
    
    for (int i = 0; i < arraySizes[0]; i++) {
        int num = arrays[0][i];
        bool foundInAll = true;
        
        for (int j = 1; j < arraysSize; j++) {
            bool found = false;
            for (int k = 0; k < arraySizes[j]; k++) {
                if (arrays[j][k] == num) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                foundInAll = false;
                break;
            }
        }
        
        if (foundInAll) {
            result[(*returnSize)++] = num;
        }
    }
    
    return result;
}

int main() {
    // Simplified input parsing for demonstration
    int arraysSize = 3;
    int* arraySizes = (int*)malloc(3 * sizeof(int));
    arraySizes[0] = 4; arraySizes[1] = 3; arraySizes[2] = 3;
    
    int** arrays = (int**)malloc(3 * sizeof(int*));
    arrays[0] = (int*)malloc(4 * sizeof(int));
    arrays[0][0] = 1; arrays[0][1] = 2; arrays[0][2] = 3; arrays[0][3] = 4;
    arrays[1] = (int*)malloc(3 * sizeof(int));
    arrays[1][0] = 1; arrays[1][1] = 2; arrays[1][2] = 3;
    arrays[2] = (int*)malloc(3 * sizeof(int));
    arrays[2][0] = 1; arrays[2][1] = 2; arrays[2][2] = 4;
    
    int returnSize;
    int* result = solution(arrays, arraySizes, arraysSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × k)

n arrays, m average length, k elements to check - nested loops

✓ Linear Growth

Space Complexity

O(1)

Only using result array, no extra data structures

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Each Element — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler