LeetCode 3043 - Find the Length of the Longest Common Prefix

Difficulty: 🟡 Medium
Topics: Array, Hash Table, String, Trie

Solution

Problem Understanding

We are given two arrays of positive integers, arr1 and arr2. The task is to determine the maximum length of a common digit prefix between any pair of numbers (x, y) where x comes from arr1 and y comes from arr2.

A prefix of a number means taking digits from the beginning, moving left to right, without skipping digits. For example, for the number 12345, the prefixes are 1, 12, 123, 1234, and 12345.

A common prefix between two integers exists if both numbers start with the same sequence of digits. For example:

5655359 and 56554 share prefixes 5, 56, 565, and 5655
1223 and 43456 share nothing because their first digits already differ

The goal is not to find the prefix itself, but rather the length of the longest such prefix across all possible cross-array pairs.

For example, if one number starts with 100 and another starts with 1000, then their longest common prefix is 100, whose length is 3.

The constraints are important:

Each array can contain up to 5 × 10^4 elements
Each number can be as large as 10^8

Since numbers are at most 9 digits long, operations involving digit traversal are relatively cheap. However, comparing every pair of elements between the arrays would involve up to:

$$5 \times 10^4 \times 5 \times 10^4 = 2.5 \times 10^9$$

comparisons, which is far too large.

Several edge cases matter:

The arrays may share no common starting digit, in which case the answer is 0
One number may be a complete prefix of another, such as 100 and 1000
Multiple numbers may share prefixes, but only the maximum prefix length matters
Since all integers are guaranteed to be positive, we never need to handle negative signs or leading zeros

Approaches

Brute Force Approach

A direct solution is to compare every number in arr1 with every number in arr2.

For each pair:

Convert both numbers into strings
Compare characters from left to right
Count how many digits match before the first mismatch
Track the maximum prefix length found

This approach is correct because it explicitly checks every possible pair and computes the exact longest common prefix for each one.

However, it is far too slow.

If n = len(arr1) and m = len(arr2), we would perform O(n × m) comparisons. Since each number has at most 9 digits, each comparison costs O(9), which is effectively constant.

The total complexity becomes:

$$O(n \times m)$$

With both arrays near 50,000 elements, this can reach billions of comparisons.

Key Insight

Instead of comparing every pair individually, observe that a common prefix only depends on prefixes themselves.

Suppose we generate all prefixes of numbers in arr1 and store them in a hash set.

For example:

100 → {1, 10, 100}

1234 → {1, 12, 123, 1234}

Then, for each number in arr2, we repeatedly trim digits from the right and check whether the remaining prefix exists in the set.

Example:

For 1000:

Check 1000
Check 100
Check 10
Check 1

As soon as we find a match, we know that prefix exists in some number from arr1.

Since each number has at most 9 digits, generating and checking prefixes is extremely cheap.

This avoids pairwise comparison entirely.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Compare every pair explicitly
Optimal	O((n + m) × d)	O(n × d)	Store prefixes in a hash set, where `d ≤ 9`

Here, d is the maximum number of digits in a number, which is at most 9.

Algorithm Walkthrough

Optimal Algorithm

Create an empty hash set called prefixes.

This set will store every possible prefix generated from numbers in arr1. A hash set gives O(1) average lookup time, which makes prefix checking very efficient. 2. Process every number in arr1.

For each number, repeatedly add the current value to the set and remove the last digit using integer division by 10.

For example:

1234 → 1234 → 123 → 12 → 1

Each intermediate value represents a valid prefix. 3. Initialize max_length = 0.

This variable tracks the best answer found so far. 4. Process every number in arr2.

For each number, repeatedly check whether the current value exists in the prefix set.

If it exists, then we found a common prefix with some number in arr1. 5. Update the answer.

When a match is found, compute the prefix length using:

len(str(prefix))

Update max_length if this length is larger. 6. Continue removing digits from the right.

If no match exists, divide by 10 and try again. 7. Return max_length.

If no common prefix was ever found, it remains 0.

Why it works

The key invariant is that the hash set contains every possible prefix from every number in arr1. Therefore, when we examine a number in arr2, any valid common prefix must appear in that set.

By checking all progressively shorter prefixes of each number in arr2, we guarantee that we eventually find the longest possible shared prefix for that number. Taking the maximum over all numbers ensures the final result is globally optimal.

Python Solution

from typing import List

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        prefixes = set()

        # Store all prefixes from arr1
        for num in arr1:
            while num > 0:
                prefixes.add(num)
                num //= 10

        max_length = 0

        # Find longest matching prefix in arr2
        for num in arr2:
            current = num

            while current > 0:
                if current in prefixes:
                    max_length = max(
                        max_length,
                        len(str(current))
                    )
                    break

                current //= 10

        return max_length

The implementation begins by constructing a hash set containing every possible prefix from arr1. Instead of converting numbers into strings and slicing prefixes, we repeatedly remove the last digit using integer division by 10.

For example, 12345 becomes:

12345 → 1234 → 123 → 12 → 1

Each of these values is inserted into the set.

After preprocessing, we iterate through arr2. For each number, we repeatedly shorten it from the right until we find a prefix that exists in the set.

Once a match is found, we compute its digit length and update the global answer. We immediately stop checking shorter prefixes because the first match encountered is already the longest prefix for that number.

Finally, we return the maximum length found.

Go Solution

func longestCommonPrefix(arr1 []int, arr2 []int) int {
	prefixes := make(map[int]struct{})

	// Store all prefixes from arr1
	for _, num := range arr1 {
		for num > 0 {
			prefixes[num] = struct{}{}
			num /= 10
		}
	}

	maxLength := 0

	// Find longest matching prefix in arr2
	for _, num := range arr2 {
		current := num

		for current > 0 {
			if _, exists := prefixes[current]; exists {
				length := len([]byte(string(rune(current))))

				// Calculate digit count
				temp := current
				digits := 0
				for temp > 0 {
					digits++
					temp /= 10
				}

				if digits > maxLength {
					maxLength = digits
				}

				break
			}

			current /= 10
		}
	}

	return maxLength
}

The Go implementation follows the same logic as Python, using a map[int]struct{} as a hash set.

One implementation difference is digit counting. Go does not have a built in equivalent of Python's len(str(num)), so we count digits manually using repeated division by 10.

Since the maximum integer value is only 10^8, integer overflow is not a concern.

Worked Examples

Example 1

Input

arr1 = [1,10,100]
arr2 = [1000]

Step 1: Build Prefix Set

Number	Generated Prefixes
1	{1}
10	{10, 1}
100	{100, 10, 1}

Final set:

{1, 10, 100}

Step 2: Process `1000`

Current Value	Exists in Set?	Action
1000	No	Divide by 10
100	Yes	Update answer = 3

Result:

Example 2

Input

arr1 = [1,2,3]
arr2 = [4,4,4]

Step 1: Build Prefix Set

{1, 2, 3}

Step 2: Process Each `4`

Current Value	Exists in Set?
4	No

No match is ever found.

Result:

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + m) × d)	Each number contributes at most `d ≤ 9` prefix operations
Space	O(n × d)	Hash set stores all prefixes from `arr1`

The crucial observation is that each number has at most 9 digits. This means every insertion or lookup chain is bounded by a tiny constant factor.

Even with 50,000 elements, the algorithm remains extremely efficient because we never compare numbers pairwise.

Test Cases

sol = Solution()

assert sol.longestCommonPrefix([1, 10, 100], [1000]) == 3  # provided example
assert sol.longestCommonPrefix([1, 2, 3], [4, 4, 4]) == 0  # no common prefix

assert sol.longestCommonPrefix([123], [123]) == 3  # exact same number
assert sol.longestCommonPrefix([100], [1000]) == 3  # full number is prefix
assert sol.longestCommonPrefix([12, 34], [1299]) == 2  # partial prefix match
assert sol.longestCommonPrefix([98765], [98]) == 2  # shorter number is prefix
assert sol.longestCommonPrefix([1], [99999]) == 0  # no overlap
assert sol.longestCommonPrefix([111, 112], [11]) == 2  # shared shorter prefix
assert sol.longestCommonPrefix([12345], [12399, 1234]) == 4  # multiple candidates
assert sol.longestCommonPrefix([99999999], [99999998]) == 7  # long prefix
assert sol.longestCommonPrefix([8], [8]) == 1  # smallest valid match

Test	Why
`[1,10,100], [1000]`	Validates provided example
`[1,2,3], [4,4,4]`	Confirms no common prefix
`[123], [123]`	Exact match
`[100], [1000]`	One number fully prefixes another
`[12,34], [1299]`	Partial match
`[98765], [98]`	Shorter number as prefix
`[1], [99999]`	No overlap
`[111,112], [11]`	Shared shorter prefix
`[12345], [12399,1234]`	Multiple candidates
`[99999999], [99999998]`	Long shared prefix
`[8], [8]`	Smallest valid positive input

Edge Cases

No Common Prefix Exists

A common mistake is assuming that matching digits will always exist. Consider:

arr1 = [1, 2, 3]
arr2 = [9, 8, 7]

No number shares even the first digit. The implementation handles this naturally because every lookup fails, so max_length remains 0.

One Number Is Completely a Prefix of Another

Cases like:

arr1 = [100]
arr2 = [1000]

can be mishandled if an implementation only compares equal length prefixes. Here, 100 is entirely contained at the beginning of 1000.

The algorithm works correctly because it repeatedly trims digits from 1000 until it finds 100 in the set.

Multiple Overlapping Prefixes

Consider:

arr1 = [12345]
arr2 = [12399]

The shared prefixes are:

1, 12, 123

A naive approach might stop too early or incorrectly return the shortest match.

This implementation checks from the longest possible prefix downward by progressively removing digits. Therefore, the first successful lookup is guaranteed to be the longest valid prefix, ensuring correctness.

LeetCode 3043 - Find the Length of the Longest Common Prefix

Solution

Problem Understanding

Approaches

Brute Force Approach

Key Insight

Algorithm Walkthrough

Optimal Algorithm

Why it works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: Build Prefix Set

Step 2: Process 1000

Example 2

Step 1: Build Prefix Set

Step 2: Process Each 4

Complexity Analysis

Test Cases

Edge Cases

No Common Prefix Exists

One Number Is Completely a Prefix of Another

Multiple Overlapping Prefixes

Step 2: Process `1000`

Step 2: Process Each `4`