Problem Description

You have two arrays arr1 and arr2 containing positive integers.

A prefix of a positive integer is formed by taking one or more consecutive digits starting from the leftmost digit. For instance, 123 is a prefix of 12345, but 234 is not since it doesn't start from the leftmost digit.

A common prefix between two integers a and b is an integer c that serves as a prefix for both numbers. For example, the integers 5655359 and 56554 share common prefixes 5, 56, 565, and 5655. However, 1223 and 43456 have no common prefix at all.

Your task is to find the longest common prefix across all possible pairs (x, y) where x comes from arr1 and y comes from arr2. You need to return the length (number of digits) of this longest common prefix. If no pairs share any common prefix, return 0.

For example:

• If arr1 = [1, 10, 100] and arr2 = [1000], the pairs would be (1, 1000), (10, 1000), and (100, 1000). The common prefixes are 1, 10, and 100 respectively, with the longest being 100 having length 3.
• If arr1 = [1, 2, 3] and arr2 = [4, 4, 4], no pairs share a common prefix, so the answer would be 0.

Intuition

The key insight is that we need to check all possible prefixes efficiently. If we were to compare every number in arr1 with every number in arr2 and extract all their prefixes, it would be computationally expensive.

Instead, we can think about this problem differently. For any number, we can generate all its prefixes by repeatedly dividing by 10. For example, the number 12345 has prefixes: 12345, 1234, 123, 12, and 1. We get these by doing 12345 // 10 = 1234, 1234 // 10 = 123, and so on.

Since we need to find common prefixes between numbers from two arrays, we can pre-compute all possible prefixes from one array and store them for quick lookup. A hash table (set) is perfect for this because it allows O(1) lookup time.

The strategy becomes:

1. Generate all prefixes for every number in arr1 and store them in a set. This way, we have all potential prefix candidates from arr1 ready.
2. For each number in arr2, generate its prefixes one by one (starting from the number itself and dividing by 10 repeatedly).
3. For each prefix of a number from arr2, check if it exists in our set. The first match we find will be the longest common prefix for that particular pair (since we're checking from longest to shortest).
4. Keep track of the maximum length among all common prefixes found.

This approach is efficient because we only need to generate prefixes once for arr1 and store them, then for each number in arr2, we can quickly check which of its prefixes exist in our set.

Learn more about Trie patterns.

Solution Approach

The implementation uses a hash table (set in Python) to efficiently store and lookup prefixes.

Step 1: Build the prefix set from arr1

s = set()
for x in arr1:
    while x:
        s.add(x)
        x //= 10

For each number x in arr1, we extract all its prefixes by repeatedly dividing by 10. For example, if x = 12345:

• First iteration: add 12345 to set, then x = 12345 // 10 = 1234
• Second iteration: add 1234 to set, then x = 1234 // 10 = 123
• Third iteration: add 123 to set, then x = 123 // 10 = 12
• Fourth iteration: add 12 to set, then x = 12 // 10 = 1
• Fifth iteration: add 1 to set, then x = 1 // 10 = 0
• Loop terminates when x becomes 0

Step 2: Find the longest common prefix with arr2

ans = 0
for x in arr2:
    while x:
        if x in s:
            ans = max(ans, len(str(x)))
            break
        x //= 10

For each number x in arr2, we check its prefixes from longest to shortest:

• Start with the number itself
• If it exists in the set s, we've found a common prefix
• Calculate its length using len(str(x)) and update the maximum if needed
• Use break to stop checking shorter prefixes (since we want the longest one for this number)
• If not found, divide by 10 to get the next shorter prefix and continue

The key optimization here is the break statement. Once we find a common prefix for a number from arr2, we don't need to check its shorter prefixes since we're looking for the longest one.

Time Complexity: O(m * log M + n * log N) where m and n are the lengths of arr1 and arr2, and M and N are the maximum values in the arrays. The log factor comes from the number of digits in each number.

Space Complexity: O(m * log M) for storing all prefixes of numbers in arr1.

Example Walkthrough

Let's walk through a concrete example with arr1 = [12, 345, 1234] and arr2 = [3456, 123, 45].

Step 1: Build prefix set from arr1

Starting with an empty set s = {}:

For x = 12:

• Add 12 to set: s = {12}
• x = 12 // 10 = 1
• Add 1 to set: s = {12, 1}
• x = 1 // 10 = 0 (stop)

For x = 345:

• Add 345 to set: s = {12, 1, 345}
• x = 345 // 10 = 34
• Add 34 to set: s = {12, 1, 345, 34}
• x = 34 // 10 = 3
• Add 3 to set: s = {12, 1, 345, 34, 3}
• x = 3 // 10 = 0 (stop)

For x = 1234:

• Add 1234 to set: s = {12, 1, 345, 34, 3, 1234}
• x = 1234 // 10 = 123
• Add 123 to set: s = {12, 1, 345, 34, 3, 1234, 123}
• x = 123 // 10 = 12
• Add 12 to set (already exists): s = {12, 1, 345, 34, 3, 1234, 123}
• x = 12 // 10 = 1
• Add 1 to set (already exists): s = {12, 1, 345, 34, 3, 1234, 123}
• x = 1 // 10 = 0 (stop)

Final prefix set: s = {12, 1, 345, 34, 3, 1234, 123}

Step 2: Find longest common prefix with arr2

Initialize ans = 0

For x = 3456:

• Check if 3456 in s? No
• x = 3456 // 10 = 345
• Check if 345 in s? Yes!
• Update ans = max(0, len("345")) = max(0, 3) = 3
• Break (don't check shorter prefixes)

For x = 123:

• Check if 123 in s? Yes!
• Update ans = max(3, len("123")) = max(3, 3) = 3
• Break

For x = 45:

• Check if 45 in s? No
• x = 45 // 10 = 4
• Check if 4 in s? No
• x = 4 // 10 = 0 (stop)
• No common prefix found for this number

Result: The longest common prefix has length 3 (from either the pair (345, 3456) with common prefix "345", or the pair (1234, 123) with common prefix "123").

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × log M + n × log N)

The algorithm consists of two main phases:

1. Building the prefix set from arr1: For each number in arr1, we repeatedly divide by 10 until the number becomes 0. Each number x in arr1 has approximately log₁₀(x) digits, so we perform that many divisions. In the worst case, the maximum value M in arr1 requires O(log M) operations. Since we process all m elements in arr1, this phase takes O(m × log M) time.

2. Checking prefixes from arr2: For each number in arr2, we again repeatedly divide by 10 while checking if the resulting number exists in the set. Each lookup in the set is O(1). In the worst case, we check all prefixes of a number, which is O(log N) operations where N is the maximum value in arr2. Processing all n elements in arr2 takes O(n × log N) time.

Space Complexity: O(m × log M)

The space is dominated by the set s that stores all possible prefixes from arr1. For each number in arr1, we store all its prefixes (obtained by repeatedly dividing by 10). A number with value x generates approximately log₁₀(x) prefixes. In the worst case, with m elements and maximum value M, we store up to O(m × log M) unique prefixes in the set.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Breaking After Finding First Match

The Problem: A common mistake is to continue checking all prefixes of a number from arr2 even after finding a match, which leads to incorrect results.

# INCORRECT - continues checking shorter prefixes
for num in arr2:
    while num > 0:
        if num in prefix_set:
            max_length = max(max_length, len(str(num)))
            # Missing break here!
        num //= 10

Why it's wrong: When we find that 12345 is a common prefix, we don't want to also check 1234, 123, 12, and 1. The inner loop would update max_length multiple times for the same number, but with decreasing lengths, which doesn't affect correctness in this case but is inefficient.

The Fix: Add a break statement immediately after finding a match to ensure we only consider the longest prefix for each number in arr2.

Pitfall 2: Using String Operations Instead of Integer Division

The Problem: Converting numbers to strings for prefix generation can be less efficient and more error-prone.

# INEFFICIENT approach
prefix_set = set()
for num in arr1:
    str_num = str(num)
    for i in range(1, len(str_num) + 1):
        prefix_set.add(int(str_num[:i]))

Why it's suboptimal:

• String slicing and conversion between int and string adds overhead
• More complex logic that's harder to understand
• Potential for off-by-one errors with string indices

The Fix: Use integer division by 10, which is more efficient and cleaner.

Pitfall 3: Forgetting to Handle Zero After Division

The Problem: Not properly terminating the loop when the number becomes 0.

# INCORRECT - might cause infinite loop without proper condition
for num in arr1:
    while True:  # Wrong condition
        prefix_set.add(num)
        num //= 10
        # Loop never terminates when num becomes 0

The Fix: Use while num > 0 or while num to ensure the loop terminates when the number becomes 0 after repeated division.

Pitfall 4: Calculating Length Incorrectly

The Problem: Using mathematical operations to calculate digit count instead of string conversion.

# ERROR-PRONE approach
import math
length = int(math.log10(num)) + 1  # Fails for num = 0

Why it's problematic:

• math.log10(0) raises a domain error
• Requires special handling for edge cases
• More complex than necessary

The Fix: Use len(str(num)) which handles all cases correctly and is more readable.