Find the Length of the Longest Common Prefix — Solution
Find the Length of the Longest Common Prefix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Length of the Longest Common Prefix is a medium coding problem on arrays, strings and hash table, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Hash Table, Trie
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A prefix of a positive integer is a number formed by one or more of its leading digits: 123 is a prefix of 12345, while 234 is not. A common prefix of two integers is a prefix of both — 5655359 and 56554 share the prefixes 5, 56, 565 and 5655, but 1223 and 43456 share none.
You are given two arrays of positive integers arr1 and arr2. Over all pairs (x, y) with x from arr1 and y from arr2, return the number of digits of the longest common prefix, or 0 if no pair has one.
Example 1
Input: arr1 = [1,10,100], arr2 = [1000]
Output: 3
Explanation: `100` and `1000` share the prefix 100, three digits long.
Example 2
Input: arr1 = [1,2,3], arr2 = [4,4,4]
Output: 0
Example 3
Input: arr1 = [12345,7], arr2 = [12399,70]
Output: 3
Explanation: `12345` and `12399` share 123; `7` and `70` share only 7.
Constraints
1 <= arr1.length, arr2.length <= 5 * 10^41 <= arr1[i], arr2[i] <= 10^8
Hints for Find the Length of the Longest Common Prefix
Hint 1
Comparing every pair is up to 2.5 · 10^9 comparisons. But each number has at most 9 prefixes.
Hint 2
Put every prefix of every
arr1element into a hash set — strip the last digit with/ 10until nothing is left.Hint 3
For each
yinarr2, strip digits from the end until what remains is in the set; the digit count of that survivor is a candidate answer.
How to solve Find the Length of the Longest Common Prefix
Numeric prefixes are what you get by repeatedly dividing by 10. Store all prefixes of arr1 in a set, then for each element of arr2 find its longest prefix in the set by stripping digits from the end.
Approach
- For each
xinarr1, insertx, x / 10, x / 100, …(while positive) into a set. - For each
yinarr2, whiley > 0andyis not in the set, sety = y / 10. - If
y > 0, its digit count is a common-prefix length; keep the maximum. - Return the maximum (0 if nothing matched).
Why it works
A common prefix of x and y is a value that is both a prefix of x (so in the set) and a prefix of y. Stripping y from the longest prefix down finds its longest prefix that lies in the set — that is, the longest prefix y shares with any x.
Complexity
- Time —
O((n + m) · D) with D ≤ 9 digits - Space —
O(n · D)
Pitfalls
- Matching digits as substrings anywhere (rather than leading digits) is wrong — 234 is not a prefix of 12345.
- Prefixes are compared as numbers, which is safe because no number has leading zeros.
- A trie of digit strings works too, at a larger constant.
Reference solution
Python
from typing import List
def longestCommonPrefix(arr1: List[int], arr2: List[int]) -> int:
prefixes = set()
for x in arr1:
while x > 0:
prefixes.add(x)
x //= 10
best = 0
for y in arr2:
while y > 0 and y not in prefixes:
y //= 10
if y > 0:
best = max(best, len(str(y)))
return bestJava
public static int longestCommonPrefix(int[] arr1, int[] arr2) {
HashSet<Integer> prefixes = new HashSet<>();
for (int x : arr1) for (int v = x; v > 0; v /= 10) prefixes.add(v);
int best = 0;
for (int y : arr2) {
int v = y;
while (v > 0 && !prefixes.contains(v)) v /= 10;
if (v > 0) best = Math.max(best, String.valueOf(v).length());
}
return best;
}C++
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
unordered_set<int> prefixes;
for (int x : arr1) for (int v = x; v > 0; v /= 10) prefixes.insert(v);
int best = 0;
for (int y : arr2) {
int v = y;
while (v > 0 && !prefixes.count(v)) v /= 10;
if (v > 0) best = max(best, (int) to_string(v).size());
}
return best;
}JavaScript
var longestCommonPrefix = function(arr1, arr2) {
var prefixes = new Set();
for (var i = 0; i < arr1.length; i++) {
for (var x = arr1[i]; x > 0; x = Math.floor(x / 10)) prefixes.add(x);
}
var best = 0;
for (var j = 0; j < arr2.length; j++) {
var y = arr2[j];
while (y > 0 && !prefixes.has(y)) y = Math.floor(y / 10);
if (y > 0 && String(y).length > best) best = String(y).length;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.