Longest Common Subsequence Between Sorted Arrays - Solution & Explanation

Problem Overview: You are given multiple arrays where each array is already sorted in strictly increasing order. The task is to return all numbers that appear in every array. The result itself forms the longest common subsequence because the arrays are sorted and elements keep their relative order.

Approach 1: Intersection with Binary Search (O(n log m) time, O(1) extra space)

Use the first array as the reference. For each value in this array, check whether it exists in every other array. Since all arrays are sorted, you can perform a binary search in each remaining array. If the value appears in all arrays, append it to the result. This approach works because the sorted property guarantees efficient lookup using logarithmic search. However, the repeated binary searches increase the overall runtime when the number of arrays grows. This technique is still useful when you want constant extra memory and arrays are large but few.

Approach 2: Counting with Hash Map (O(T) time, O(U) space)

The most practical solution uses a frequency counter. Iterate through every array and increment a counter for each value using a hash map. Because each array is strictly increasing, every value appears at most once per array, so you can safely increment the count without worrying about duplicates inside the same array. After processing all arrays, any value whose frequency equals the number of arrays appears in every array.

The key insight: the problem reduces to tracking how many arrays contain a given number. Instead of comparing arrays pairwise, the counting structure aggregates occurrences globally. The total runtime becomes proportional to the total number of elements across all arrays, often written as O(T). Space complexity is O(U), where U is the number of unique values seen.

This approach relies on fast insert and lookup operations from a hash table. Iterating through arrays is straightforward using standard array traversal. Conceptually, this is also a classic counting pattern where frequencies determine the final result.

Recommended for interviews: The counting approach is what most interviewers expect. It shows you recognize that the task is essentially a frequency aggregation problem rather than a subsequence DP problem. Mentioning the binary-search intersection first demonstrates you considered the sorted property, but implementing the hash map counting solution shows stronger algorithmic judgment and produces the cleanest O(T) runtime.