Find the Length of the Longest Common Prefix
Understanding the Problem
We have two arrays of positive integers. For every possible pair where one number comes from arr1 and the other from arr2, we need to find how many leading digits they share, and return the maximum such count across all pairs.
For example, if arr1 has the number 12345 and arr2 has 12367, their common prefix is "123", so they share 3 leading digits. We want the pair across the two arrays that shares the longest such leading sequence.
We don't need to check every pair individually. The prefixes of a number form a small set (at most 9 of them). If we store every prefix that appears in one array, we can look up whether the other array's numbers reuse any of those prefixes. This turns "compare all pairs" into "which prefixes do the two arrays have in common?"
Key Constraints:
1 <= arr1.length, arr2.length <= 5 * 10^4→ With up to 50,000 elements in each array, a brute force approach that checks all pairs would do up to 2.5 billion pair comparisons. That's too slow. We need something better than O(m * n).1 <= arr1[i], arr2[i] <= 10^8→ Each number has at most 9 digits. This means the "prefix work" per number is bounded by a small constant (at most 9 prefixes per number). Any approach that does O(d) work per number, where d is the number of digits, is effectively linear in the array size.
Approach 1: Brute Force
Intuition
For every pair (x, y) where x comes from arr1 and y comes from arr2, convert both numbers to strings and compare them character by character from the left. Count how many leading characters match, and track the maximum across all pairs.
This mirrors comparing two numbers by hand: line them up at the leftmost digit and count how many positions agree before the first mismatch.
Algorithm
- Initialize
maxLength = 0. - For each number
xinarr1: - For each number
yinarr2: - Convert both to strings.
- Compare characters from the start, counting how many match consecutively.
- Update
maxLengthwith the count if it's larger. - Return
maxLength.
Visualization and Code
Loading animation...
- Time Complexity: O(m n d). We check every pair of elements (m * n pairs), and for each pair we compare up to d digits, where d is the maximum number of digits (at most 9).
- Space Complexity: O(d). We only use temporary strings of length at most d = 9 digits. Effectively constant space.
Comparing every pair is too slow for the given constraints. The next approach precomputes all the prefixes from one array once, then reuses them for every lookup.
Approach 2: Hash Set of Prefixes
Intuition
Instead of comparing pairs of numbers, we can split the problem into two phases. First, collect every prefix from all numbers in arr1. Then, for each number in arr2, generate its prefixes and check which ones already appear in that collection.
To generate all prefixes of a number, repeatedly divide by 10. Take 12345: dividing gives 12345, 1234, 123, 12, 1, where each division strips the last digit to produce the next shorter prefix. A prefix represented as an integer is unique, so two numbers share leading digits exactly when they produce the same prefix value.
Store all prefixes from arr1 in a hash set. Then for each number in arr2, generate its prefixes from longest to shortest and check each against the set. The longest match found across all arr2 numbers is the answer.
In Phase 2 we start from the full arr2 number and divide by 10, so we test prefixes from longest to shortest. If a prefix of length k is in the set, then every shorter prefix of the same number is also in the set (the set was built by the same divide-by-10 process on arr1). The first match is therefore the longest possible for that number, and the break skips the redundant shorter checks.
Algorithm
- Create an empty hash set
prefixSet. - For each number
xinarr1: - While
x > 0, addxtoprefixSet, then setx = x / 10. - Initialize
maxLength = 0. - For each number
yinarr2: - While
y > 0: - If
yis inprefixSet, updatemaxLengthwith the number of digits iny, then break (longest prefix for this number found). - Set
y = y / 10. - Return
maxLength.
Visualization and Code
Loading animation...
- Time Complexity: O((m + n) * d). Building the prefix set processes m numbers with up to d = 9 prefixes each. Checking arr2 does the same for n numbers. Since d <= 9, this is effectively O(m + n).
- Space Complexity: O(m * d). The hash set stores up to d prefixes for each of the m numbers. Since d <= 9, this is effectively O(m).
The hash set stores each prefix as a separate entry, even when many numbers share the same leading digits. The next approach uses a trie, which stores shared prefixes once as a common path.
Approach 3: Trie
Intuition
A trie (prefix tree) stores prefixes as paths in a tree. Each edge represents one digit, and each path from the root to a node spells out a prefix. Building the trie from arr1 makes every prefix of every arr1 number a path, with shared leading digits collapsed onto a single shared path.
Take the number 12345. We insert the digits 1, 2, 3, 4, 5 as a path. To compare 12367 against it, we walk the trie following 1, 2, 3, then stop at digit 6 because that node has no child for 6 (it has a child for 4). The depth reached, 3, is the longest common prefix between 12367 and 12345.
Sharing is what makes this compact. If arr1 has 123, 1234, and 456, the trie stores the path 1 to 2 to 3 to 4 once rather than once per number, plus a separate branch 4 to 5 to 6.
Algorithm
- Build a trie from all numbers in
arr1: - For each number, extract its digits from left to right.
- Insert each digit as a child node, creating new nodes as needed.
- For each number in
arr2, traverse the trie: - Extract digits from left to right.
- Follow the trie path as long as matching children exist.
- The depth reached is the common prefix length for this number.
- Track and return the maximum depth across all arr2 numbers.
Visualization and Code
Loading animation...
- Time Complexity: O((m + n) * d). Building the trie processes m numbers with at most d = 9 digits. Querying processes n numbers similarly. Since d is at most 9, this is effectively O(m + n).
- Space Complexity: O(m d). The trie stores at most m d nodes in the worst case. Each node has a fixed-size array of 10 children. In practice, shared prefixes reduce this significantly.