Find the Length of the Longest Common Prefix
MedPrompt
You are given two arrays with positive integers arr1 and arr2.
A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not.
A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. For example, 5655359 and 56554 have common prefixes 565 and 5655 while 1223 and 43456 do not have a common prefix.
You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.
Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.
Example 1:
Input: arr1 = [1,10,100], arr2 = [1000]
Output: 3
Explanation: There are 3 pairs (arr1[i], arr2[j]):
- The longest common prefix of (1, 1000) is 1.
- The longest common prefix of (10, 1000) is 10.
- The longest common prefix of (100, 1000) is 100.
The longest common prefix is 100 with a length of 3.Example 2:
Input: arr1 = [1,2,3], arr2 = [4,4,4]
Output: 0
Explanation: There exists no common prefix for any pair (arr1[i], arr2[j]), hence we return 0.
Note that common prefixes between elements of the same array do not count.
Constraints:
1 <= arr1.length, arr2.length <= 5 * 1041 <= arr1[i], arr2[i] <= 108
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly implements the problem statement by checking every possible pair of numbers, one from arr1 and one from arr2.
Algorithm
- Initialize
maxLength = 0. - For each
num1inarr1:- For each
num2inarr2:- Convert
num1andnum2to stringss1ands2. - Find the length of the common prefix of
s1ands2. Let this becurrentLength. - Update
maxLength = max(maxLength, currentLength).
- Convert
- For each
- Return
maxLength.
Walkthrough
We initialize a variable maxLength to 0 to store the length of the longest common prefix found so far.
We use nested loops to iterate through every number x in arr1 and every number y in arr2.
For each pair (x, y), we calculate the length of their common prefix. A helper function can be used for this. The helper function works by converting both numbers to strings. Then, it compares them character by character to find the length of the common prefix string.
After calculating the length for a pair, we update maxLength if the current length is greater.
Finally, after checking all pairs, maxLength holds the result.
class Solution { public int longestCommonPrefix(int[] arr1, int[] arr2) { int maxLength = 0; for (int num1 : arr1) { for (int num2 : arr2) { String s1 = String.valueOf(num1); String s2 = String.valueOf(num2); int currentLength = 0; int len = Math.min(s1.length(), s2.length()); for (int i = 0; i < len; i++) { if (s1.charAt(i) == s2.charAt(i)) { currentLength++; } else { break; } } maxLength = Math.max(maxLength, currentLength); } } return maxLength; }}Complexity
Time
O(N * M * D), where `N` is the length of `arr1`, `M` is the length of `arr2`, and `D` is the maximum number of digits in a number. This is because we have nested loops for `N*M` pairs, and for each pair, we compare strings of length up to `D`. This is too slow for the given constraints.
Space
O(D) for storing the string representations of two numbers at a time during comparison.
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
This approach avoids the inefficient nested loop by pre-processing one of the arrays. We generate all possible prefixes from one array and store them in a hash set. Then, for each number in the other array, we can efficiently check for its prefixes in the hash set.
Algorithm
- Create a
HashSet<Integer>calledprefixSet. - For each
numinarr2:- Generate all its prefixes by repeatedly dividing by 10 and add them to
prefixSet.
- Generate all its prefixes by repeatedly dividing by 10 and add them to
- Initialize
maxLength = 0. - For each
numinarr1:- Check its prefixes from longest to shortest (by dividing by 10).
- If a prefix is found in
prefixSet:- Calculate its length.
- Update
maxLengthwith the new maximum length. - Break the inner loop (as we've found the longest for this
num).
- Return
maxLength.
Walkthrough
The core idea is to reduce the search time for a common prefix. Instead of comparing a number from arr1 with every number in arr2, we can check if any prefix of the arr1 number exists as a prefix in the arr2 set.
- First, we create a
HashSetof integers to store all prefixes of numbers from one of the arrays, sayarr2. - We iterate through each number
yinarr2. For eachy, we generate all its prefixes by repeatedly dividing it by 10 until it becomes 0. For example, ifyis 123, we add 123, 12, and 1 to the set. - After populating the set, we iterate through each number
xinarr1. For eachx, we check its prefixes against the set, starting from the longest prefix (the numberxitself) down to the shortest. - The first prefix we find in the set is guaranteed to be the longest common prefix for that particular
x. We calculate its length and update our globalmaxLength. We can then break and move to the next number inarr1.
import java.util.HashSet;import java.util.Set; class Solution { public int longestCommonPrefix(int[] arr1, int[] arr2) { Set<Integer> prefixSet = new HashSet<>(); for (int num : arr2) { int current = num; while (current > 0) { prefixSet.add(current); current /= 10; } } int maxLength = 0; for (int num : arr1) { int current = num; while (current > 0) { if (prefixSet.contains(current)) { maxLength = Math.max(maxLength, String.valueOf(current).length()); break; } current /= 10; } } return maxLength; }}Complexity
Time
O((N + M) * D), where `N` and `M` are the lengths of the arrays and `D` is the max number of digits. Populating the set takes `O(M * D)` and searching takes `O(N * D)`. This is efficient enough.
Space
O(M * D) to store all prefixes from `arr2` in the hash set. In the worst case, all prefixes are unique.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Relatively easy to implement using a standard hash set.
Cons
Uses extra space to store prefixes, which can be large if
arr2is large.
This is a highly optimized approach using a Trie, a tree-like data structure perfect for prefix-related problems. We insert all numbers from one array into the Trie and then search for the longest matching prefixes for numbers from the second array.
Algorithm
- Define a
TrieNodeclass with an array of 10 children. - Create a
rootTrieNode. - For each
numinarr2:- Convert
numto a strings. - Insert
sinto the Trie by traversing from therootand creating nodes as needed.
- Convert
- Initialize
maxLength = 0. - For each
numinarr1:- Convert
numto a strings. - Traverse the Trie from the
rootusing the digits ofs. - Count the number of steps (
currentLength) until a path does not exist. - Update
maxLength = max(maxLength, currentLength).
- Convert
- Return
maxLength.
Walkthrough
A Trie is a specialized tree used to store a set of strings, where paths from the root to a node represent prefixes. For this problem, we treat the numbers as strings of digits.
- First, we build a Trie by inserting all numbers from
arr2. Each node in our Trie will have up to 10 children, one for each digit (0-9). - To insert a number, we convert it to a string. Then, starting from the root of the Trie, we traverse down the tree, creating new nodes as needed for each digit.
- After building the Trie, we iterate through each number
xinarr1. For eachx, we convert it to a string and traverse the Trie from the root, following the path corresponding to its digits. - We count the length of the path we successfully traverse. The traversal stops when we can't go further (i.e., a child node for a digit doesn't exist). This length is the longest prefix of
xthat is also a prefix of some number inarr2. - We update a global
maxLengthwith the maximum length found across all numbers inarr1.
class TrieNode { TrieNode[] children = new TrieNode[10];} class Solution { public int longestCommonPrefix(int[] arr1, int[] arr2) { TrieNode root = new TrieNode(); for (int num : arr2) { String s = String.valueOf(num); TrieNode curr = root; for (char c : s.toCharArray()) { int digit = c - '0'; if (curr.children[digit] == null) { curr.children[digit] = new TrieNode(); } curr = curr.children[digit]; } } int maxLength = 0; for (int num : arr1) { String s = String.valueOf(num); TrieNode curr = root; int currentLength = 0; for (char c : s.toCharArray()) { int digit = c - '0'; if (curr.children[digit] == null) { break; } curr = curr.children[digit]; currentLength++; } maxLength = Math.max(maxLength, currentLength); } return maxLength; }}Complexity
Time
O((N + M) * D), where `N` and `M` are the lengths of the arrays and `D` is the max number of digits. Building the Trie takes `O(M * D)`, and searching takes `O(N * D)`.
Space
O(M * D) in the worst case for the Trie nodes. It can be more space-efficient than a hash set if numbers in `arr2` share many common prefixes.
Trade-offs
Pros
Highly efficient and a canonical solution for prefix-based problems.
Can be more space-efficient than a hash set.
No risk of hash collisions and potentially better performance due to memory locality.
Cons
More complex to implement from scratch compared to using a built-in hash set.
Solutions
Solution
class Solution {public int longestCommonPrefix(int[] arr1, int[] arr2) { Set<Integer> s = new HashSet<>(); for (int x : arr1) { for (; x > 0; x /= 10) { s.add(x); } } int ans = 0; for (int x : arr2) { for (; x > 0; x /= 10) { if (s.contains(x)) { ans = Math.max(ans, String.valueOf(x).length()); break; } } } return ans; }}/** * @param {number[]} arr1 * @param {number[]} arr2 * @return {number} */ var longestCommonPrefix = function ( arr1 , arr2 ) { const s = new Set (); for ( let x of arr1 ) { for (; x ; x = Math . floor ( x / 10 )) { s . add ( x ); } } let ans = 0 ; for ( let x of arr2 ) { for (; x ; x = Math . floor ( x / 10 )) { if ( s . has ( x )) { ans = Math . max ( ans , Math . floor ( Math . log10 ( x )) + 1 ); } } } return ans ; };class Solution: def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int: s = set() for x in arr1: while x: s . add(x) x //= 10 ans = 0 for x in arr2: while x: if x in s: ans = max(ans, len(str(x))) break x //= 10 return ansclass Solution {public: int longestCommonPrefix(vector<int> &arr1, vector<int> &arr2) { unordered_set<int> s; for (int x : arr1) { for (; x; x /= 10) { s.insert(x); } } int ans = 0; for (int x : arr2) { for (; x; x /= 10) { if (s.count(x)) { ans = max(ans, (int)log10(x) + 1); break; } } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.