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] <= 108Problem Overview: Given two integer arrays, the task is to determine the maximum length of a shared prefix between any number from the first array and any number from the second array. Treat each number as a string and compare their leading digits to find the longest matching prefix.
Approach 1: Brute Force Prefix Comparison (Time: O(n * m * L), Space: O(1))
Convert each number in both arrays to strings. For every pair (a, b) where a comes from the first array and b comes from the second, compare characters from left to right until the prefix breaks. Track the longest matching length encountered. The algorithm performs nested iteration across both arrays and direct character comparison, making it simple but expensive when arrays are large.
This method works well for understanding the core idea of prefix matching. However, the nested comparisons lead to quadratic pair checks. When arrays grow into thousands of elements, the runtime becomes noticeable.
Approach 2: Optimized String Comparison Using Sorting (Time: O((n + m) log(n + m) * L), Space: O(n + m))
Convert every number from both arrays into strings and place them into a combined structure while preserving their origin. Sort the strings lexicographically. In sorted order, strings with similar prefixes naturally appear next to each other. You only need to compare adjacent strings that originate from different arrays and compute their common prefix length.
The key insight is that lexicographic sorting groups similar prefixes together. Instead of checking every possible pair, you reduce comparisons to neighboring strings. Each comparison scans characters until the prefix mismatch occurs. This drastically reduces redundant checks while leveraging efficient sorting behavior.
This approach uses ideas from string ordering and structured comparisons across array elements. A more advanced alternative could use a Trie to store prefixes, but sorting keeps implementation simpler while remaining efficient.
Recommended for interviews: Start by describing the brute force pair comparison to demonstrate understanding of the prefix concept. Then move to the optimized sorting approach. Interviewers typically expect you to reduce unnecessary pair checks and leverage lexicographic ordering, which shows stronger algorithmic reasoning and practical optimization skills.
The simplest way to solve this problem is to iterate over each pair of integers from arr1 and arr2. For each pair, convert the integers to strings and compare character by character to find the common prefix. Keep a running maximum of the lengths of these prefixes.
Since we are comparing each pair, the time complexity is O(n * m * k), where n is the length of arr1, m is the length of arr2, and k is the length of the longest number when converted to a string. Space complexity is O(1) as we're only storing a few additional variables.
This C solution utilizes a nested loop to iterate through each combination of numbers from arr1 and arr2. For each combination, it finds the common prefix length using a helper function that compares the string representations of the numbers. The maximum prefix length found is returned.
Time complexity: O(n * m * k), Space complexity: O(1)
This optimized approach leverages sorting of the input arrays to reduce comparisons. After sorting, only consecutive elements can potentially have a longer common prefix with elements of the other array than already found max. This minimizes the number of comparisons, improving efficiency over the brute force approach.
Time complexity may approach O(n + m) in the best-case scenario where common prefixes are found early, but in the worst case it remains approximately O(n * m). The space complexity is still O(1).
This C solution uses sorting to increase the efficiency of comparisons. Once the arrays are sorted, potential longer common prefixes only appear among consecutive elements, reducing unnecessary computations and leading to quicker results.
Average Time complexity: O(n log n + m log m + n + m), Space complexity: O(1)
We can use a hash table to store all the prefixes of the numbers in arr1. Then, we traverse all the numbers x in arr2. For each number x, we start from the highest bit and gradually decrease, checking whether it exists in the hash table. If it does, we have found a common prefix, and we can update the answer accordingly.
The time complexity is O(m times log M + n times log N), and the space complexity is O(m times log M). Here, m and n are the lengths of arr1 and arr2 respectively, and M and N are the maximum values in arr1 and arr2 respectively.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time complexity: O(n * m * k), Space complexity: O(1) |
| Optimized String Comparison Approach Using Sorting | Average Time complexity: O(n log n + m log m + n + m), Space complexity: O(1) |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Comparison | O(n * m * L) | O(1) | Small input sizes or when explaining the base idea in interviews |
| Optimized String Comparison Using Sorting | O((n + m) log(n + m) * L) | O(n + m) | General case with larger arrays where reducing pair comparisons improves performance |
Find the Length of the Longest Common Prefix - Leetcode 3043 - Python • NeetCodeIO • 14,734 views views
Watch 9 more video solutions →Practice Find the Length of the Longest Common Prefix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor