Longest Common Subsequence Between Sorted Arrays

Longest Common Subsequence Between Sorted Arrays

What is this problem about?

In this variation of the LCS problem, you are given an array of arrays, where each individual array is filled with integers and is already sorted in strictly increasing order. Your objective is to find the longest common subsequence shared by all the arrays. Because the arrays are strictly increasing, a "subsequence" across all of them simply boils down to finding the exact elements that are present in every single array.

Why is this asked in interviews?

Interviewers ask this question to see if candidates can recognize when to drop a heavy, complex algorithm (like 2D Dynamic Programming) in favor of a simpler, more efficient one based on the given constraints. By stating the arrays are "sorted" and "strictly increasing", the problem transforms from a complex string alignment task into an array intersection task. It tests observational skills and knowledge of Hash Tables and pointers.

Algorithmic pattern used

The best approach leverages Counting / Hash Tables or Multiple Pointers. Because elements are strictly increasing, an element cannot appear twice in the same array. Therefore, if there are N arrays, an integer is part of the common subsequence if and only if its frequency count across all arrays is exactly N. You simply iterate through all elements, count their frequencies, and output the ones that reach a count of N.

Example explanation

Given 3 arrays: Array 1: [1, 3, 4, 8] Array 2: [2, 3, 4, 7, 8] Array 3: [3, 4, 5, 8]

We can use a hash map to count the frequencies:

• 1 appears 1 time.
• 2 appears 1 time.
• 3 appears 3 times.
• 4 appears 3 times.
• 8 appears 3 times. Since we have 3 arrays, we look for numbers with a frequency of 3. Those are [3, 4, 8]. Because we process them from the naturally sorted arrays, our resulting sequence is inherently the longest common subsequence!

Common mistakes candidates make

The most glaring mistake is applying the classic $O(N \times M)$ Dynamic Programming solution meant for unsorted strings. DP is completely overkill here and wastes execution time and memory. Another mistake is forgetting that while Hash Tables are great, you can also solve this using a frequency array if the integer ranges are small, which provides even faster lookup times.

Interview preparation tip

When tackling the Longest Common Subsequence Between Sorted Arrays interview pattern, always pay close attention to adjectives in the prompt like "sorted" or "strictly increasing". These words are giant hints that you can utilize $O(N)$ counting techniques or binary searches rather than heavy $O(N^2)$ algorithmic templates.