DSA problem
Find the Length of the Longest Common Prefix
You are given two arrays arr1 and arr2 of positive integers. A common prefix of two integers x and y is an integer that is a prefix of both, where the prefix is taken on the decimal-digit string representation reading from the most significant digit. For example, the common prefixes of 123 and 12345 are 1 and 12 (the longest length is 2), while 52 and 539 share only 5 (length 1).
Return the length of the longest common prefix between any pair (x, y) where x is from arr1 and y is from arr2. If no pair shares any prefix at all, return 0.
A brute-force solution compares every pair, costing O(n * m * L) where L is the number of digits — far too slow for arrays of size 5 * 10^4. The trick is to recognise that "longest common prefix" is exactly the operation a trie excels at when the keys are digit strings.
Insert every arr1 number into a trie of digits (a 10-child trie, one slot per decimal digit). Then for each number y in arr2, walk the trie one digit at a time from MSB to LSB; the number of digits successfully matched along the path equals the length of the longest common prefix between y and any arr1 value. Take the maximum across all queries. Total time is O(d1 + d2) where d1 and d2 are the total digit counts of arr1 and arr2 respectively.
Examples
arr1 = [1,10,100], arr2 = [1000]3arr1 = [1,2,3], arr2 = [4,4,4]0arr1 = [123,456,789], arr2 = [12,45,7890]3Constraints
- 1 <= arr1.length, arr2.length <= 5 * 10^4
- 1 <= arr1[i], arr2[i] <= 10^8
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.