MediumArrayHash TableStringTrieUpdated Sep 2026

3043. Find the Length of the Longest Common Prefix

Asked at Databricks, Capital One

Difficulty

Medium

Time

O((m + n) * d)

Space

O(m * d)

Pattern

Array

Companies

2

Problem

You are given two arrays of positive integers, arr1 and arr2. A prefix of a number is what you get by keeping one or more of its digits starting from the left. For example, 12, 123 and 1234 are all prefixes of 1234.

A common prefix of two numbers is a value that is a prefix of both of them. For example, 56 and 5655 share the prefixes 5 and 56.

Look at every pair (x, y) where x comes from arr1 and y comes from arr2. Return the number of digits in the longest common prefix found across all such pairs. If no pair shares even one leading digit, return 0. Note that two numbers from the same array do not count as a pair.

Matching leading digits across the two arrays

arr1110100012The best partner for 1000 is 100.arr2100001000 starts with the digits 1, 0, 0 — the same startas 100.
1000 shares its first three digits with 100, so the longest common prefix has length 3.

Constraints

  • ●1 <= arr1.length, arr2.length <= 5 * 10^4
  • ●1 <= arr1[i], arr2[i] <= 10^8

Examples

Example 1
Inputarr1 = [1,10,100], arr2 = [1000]
Output3
WhyThe only partner is 1000. It shares prefix 1 with 1 (length 1), prefix 10 with 10 (length 2), and prefix 100 with 100 (length 3). The best is 3.
Example 2
Inputarr1 = [1,2,3], arr2 = [4,4,4]
Output0
WhyEvery number in arr1 starts with 1, 2 or 3, and every number in arr2 starts with 4. No pair shares a first digit, so the answer is 0.

Asked At

2 companies
CompanyDifficulty
DatabricksMediumView all Databricks questions →
Capital OneMediumView all Capital One questions →

How to Think About It

1

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).

2

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.

3

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.

4

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.

5

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.

6

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.

  1. Insert all numbers from arr1 into a hash set.
  2. For each number in arr2:
    a. Generate all prefixes by repeatedly dividing by 10.
    b. For each prefix, check if it exists in the arr1 set.
    c. Track the maximum prefix length found.
  3. Return the global maximum.

Approach 2: Trie.

  1. Insert all numbers from arr1 as strings into a Trie.
  2. For each number in arr2, traverse the Trie character by character until no match.
  3. 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.

Store arr1 prefixes, then shrink each arr2 number

prefix set from arr1110100frontbackAll prefixes of 1, 10 and 100 go into a hash set.1000 not in set100 in set → length 3Cut the last digit off 1000 until a prefix is found; stopat the first hit.while num > 0: if num in prefixes: best = max(best, len(str(num))) num //= 10
Put every prefix of arr1 into a set, then cut digits off each arr2 number until a prefix is found.
ComplexityTime O((m + n) * d)Space O(m * d)Each number is chopped into at most d prefixes (d is the digit count, at most 9 here), and the set stores all prefixes of arr1.

What Trips People Up in Real Interviews

1

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".

2

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.

3

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.

4

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.

5

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

O((m + n) * d) time
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 best

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O((m + n) * d) time and O(m * d) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Find the Length of the Longest Common Prefix?

Find the Length of the Longest Common Prefix is asked at Databricks, Capital One. 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.