Watch 10 video solutions for Find the Length of the Longest Common Prefix, a medium level problem involving Array, Hash Table, String. This walkthrough by NeetCodeIO has 14,734 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |