Skip to main content
Talentd

Longest Common Subsequence Between Sorted Arrays - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableCounting10 min readAsked at: Google
Practice this problem

Problem Statement

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.

 

Example 1:

Input: arrays = [[1,3,4],
                 [1,4,7,9]]
Output: [1,4]
Explanation: The longest common subsequence in the two arrays is [1,4].

Example 2:

Input: arrays = [[2,3,6,8],
                 [1,2,3,5,6,7,10],
                 [2,3,4,6,9]]
Output: [2,3,6]
Explanation: The longest common subsequence in all three arrays is [2,3,6].

Example 3:

Input: arrays = [[1,2,3,4,5],
                 [6,7,8]]
Output: []
Explanation: There is no common subsequence between the two arrays.

 

Constraints:

  • 2 <= arrays.length <= 100
  • 1 <= arrays[i].length <= 100
  • 1 <= arrays[i][j] <= 100
  • arrays[i] is sorted in strictly increasing order.

Approach Overview

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.

Solution

We note that the range of elements is [1, 100], so we can use an array cnt of length 101 to record the number of occurrences of each element.

Since each array in arrays is strictly increasing, the elements of the common subsequence must be monotonically increasing, and the number of occurrences of these elements must be equal to the length of arrays.

Therefore, we can traverse each array in arrays and count the number of occurrences of each element. Finally, traverse each element of cnt from smallest to largest. If the number of occurrences is equal to the length of arrays, then this element is one of the elements of the common subsequence, and we add it to the answer array.

After the traversal, return the answer array.

The time complexity is O(M + N), and the space complexity is O(M). Here, M is the range of elements, and in this problem, M = 101, and N is the total number of elements in the arrays.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Intersection with Binary SearchO(n log m)O(1)When arrays are sorted and you want minimal extra memory
Counting with Hash MapO(T)O(U)Best general solution; efficient when processing many arrays

Video Solution

1940. Longest Common Subsequence Between Sorted Arrays - Week 1/5 Leetcode June Challenge • Programming Live with Larry • 186 views views

Frequently Asked Questions

Is Longest Common Subsequence Between Sorted Arrays easy or hard?
The problem is typically classified as Medium. The logic is straightforward once you recognize the counting pattern, but the challenge is identifying that the subsequence requirement simplifies to finding values present in every sorted array.
Longest Common Subsequence Between Sorted Arrays Python/Java solution
In Python, use a dictionary or collections.Counter to track frequencies while iterating through arrays. In Java, use a HashMap<Integer, Integer>. Increment counts for each element and collect numbers whose count equals the number of arrays.
How to solve Longest Common Subsequence Between Sorted Arrays in O(n)?
Traverse every array and maintain a hash map that counts how many arrays contain each number. Since each array is strictly increasing, you increment the count once per element. After processing all arrays, collect numbers whose frequency equals the number of arrays. The runtime becomes linear in the total number of elements.
What is the best approach for Longest Common Subsequence Between Sorted Arrays?
The most efficient approach uses a hash map counting technique. Iterate through each array and increment the frequency of every number. Any value whose count equals the total number of arrays appears in all arrays. This runs in O(T) time where T is the total number of elements across arrays, with O(U) extra space for unique values.
Is Longest Common Subsequence Between Sorted Arrays asked at Google/Amazon/Meta?
Problems involving array intersection, hash map counting, and multi-array processing frequently appear in interviews at companies like Amazon, Google, and Meta. This specific problem tests recognition of counting patterns and efficient use of hash tables.
What data structure is used in Longest Common Subsequence Between Sorted Arrays?
The optimal solution uses a hash map (dictionary) to count occurrences of each number across arrays. Arrays are iterated sequentially, and the hash map stores how many arrays contain each value.
What is the time complexity of Longest Common Subsequence Between Sorted Arrays?
Using the optimal counting approach, the time complexity is O(T), where T is the total number of elements across all arrays. Each element is processed exactly once. Space complexity is O(U) for the hash map storing unique values.

Ready to solve this problem?

Practice Longest Common Subsequence Between Sorted Arrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Merge Two Sorted Lists