Find the Length of the Longest Common Prefix
Asked at Databricks
Problem
Given two integer arrays arr1 and arr2, return the length of the longest common prefix between any pair of elements from the two arrays. For example, the longest common prefix of 123 and 12456 is "12", so the length is 2.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
How to Think About It
Understanding common prefix: the longest common prefix of two numbers is the longest sequence of leading digits they share. 12345 and 12399 share "123" (length 3). 123 and 456 share nothing (length 0).
Brute force: for each pair (a from arr1, b from arr2), compute the common prefix length. Compare digits from the most significant position. This is O(m * n * d) where d is max digits. Works but slow.
Better: use a hash set. Insert all numbers from arr1 into a set. For each number in arr2, generate all its prefixes (by removing last digit repeatedly) and check if any prefix exists in the arr1 set. Track the maximum prefix length found.
Prefix generation: for a number like 12345, generate prefixes: 12345, 1234, 123, 12, 1. For each, check if it's in the arr1 set. The longest match is the answer for that number.
Why this works: if prefix p of number b exists in arr1 as some number a, then p is also a prefix of a (since a equals p or has more digits after p). So the common prefix of a and b is at least len(p) digits.
Alternative: use a Trie. Insert all numbers from arr1 as strings into a Trie. For each number in arr2, traverse the Trie as far as possible. The depth reached is the longest common prefix length. Trie gives O(m * d + n * d) time.
Optimal Approach
Approach 1: Hash set with prefix generation.
- Insert all numbers from
arr1into ahash set. - For each number in
arr2:
a. Generate all prefixes by repeatedly dividing by 10.
b. For each prefix, check if it exists in thearr1set.
c. Track the maximum prefix length found. - Return the global maximum.
Approach 2: Trie.
- Insert all numbers from
arr1as strings into a Trie. - For each number in
arr2, traverse the Trie character by character until no match. - The depth reached is the longest common prefix length.
Walkthrough with arr1=[1,10,100], arr2=[1000]:
- Set: {1, 10, 100}.
- For 1000: prefixes are 1000, 100, 10, 1.
- 1000 not in set. 100 in set (length 3). Max = 3.
- 10 in set (length 2). 3 > 2, keep 3.
- 1 in set (length 1). 3 > 1, keep 3.
- Return 3.
Time: O(m * d + n * d) where d is max digits (at most 10 for int). Space: O(m * d) for the set/prefixes.
What Trips People Up in Real Interviews
Confusing common prefix with common suffix. The prefix is the leading digits, not trailing. 12345 and 62345 share prefix "1" (first digit), not suffix "2345".
Generating prefixes incorrectly. For number 123, the prefixes are 123, 12, 1. Do NOT generate 23, 3, etc. — those are suffixes or substrings, not prefixes.
Forgetting that a number itself is a prefix of itself. If arr1 contains 123 and arr2 contains 123, their common prefix is "123" (length 3). The number itself is its own full prefix.
Using string conversion when integer math is cleaner. To get prefixes, repeatedly divide by 10: 123 -> 12 -> 1. This avoids string conversion overhead, though strings work fine too.
Not tracking the global maximum. You need the longest common prefix across ALL pairs, not just one. Update a global max as you process each number.
Solution Code
def longestCommonPrefix(arr1, arr2):
prefixes = set()
for num in arr1:
while num > 0:
prefixes.add(num)
num //= 10
best = 0
for num in arr2:
while num > 0:
if num in prefixes:
best = max(best, len(str(num)))
break
num //= 10
return bestFrequently Asked Questions
What is the Find the Length of the Longest Common Prefix problem?
Given two integer arrays `arr1` and `arr2`, return the length of the longest common prefix between any pair of elements from the two arrays. For example, the longest common prefix of 123 and 12456 is "12", so the length is 2.
How do you solve Find the Length of the Longest Common Prefix?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Find the Length of the Longest Common Prefix?
Find the Length of the Longest Common Prefix is asked at Databricks. It is a medium difficulty problem.
What are common mistakes on Find the Length of the Longest Common Prefix?
- Confusing common prefix with common suffix. The prefix is the leading digits, not trailing. 12345 and 62345 share prefix "1" (first digit), not suffix "2345".
- Generating prefixes incorrectly. For number 123, the prefixes are 123, 12, 1. Do NOT generate 23, 3, etc. — those are suffixes or substrings, not prefixes.
- Forgetting that a number itself is a prefix of itself. If arr1 contains 123 and arr2 contains 123, their common prefix is "123" (length 3). The number itself is its own full prefix.
- Using string conversion when integer math is cleaner. To get prefixes, repeatedly divide by 10: `123 -> 12 -> 1`. This avoids string conversion overhead, though strings work fine too.
- Not tracking the global maximum. You need the longest common prefix across ALL pairs, not just one. Update a global max as you process each number.