When working with arrays of integers, you may encounter the task of finding the length of the longest common prefix between all pairs of integers, one from each array. In this post, we’ll explore both a brute-force approach and a more optimized solution to solve this problem efficiently.

📋 Problem Statement

You are given two arrays of positive integers, arr1 and arr2. A prefix of a number is a number formed by one or more of its digits starting from the leftmost digit. For example, 123 is a prefix of 12345, but 234 is not.

Your goal is to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.

💡 Example 1:

Input: arr1 = [1, 10, 100], arr2 = [1000]
Output: 3

Explanation: 
- The longest common prefix of (1, 1000) is 1.
- The longest common prefix of (10, 1000) is 10.
- The longest common prefix of (100, 1000) is 100.
Thus, the longest common prefix is 100 with a length of 3.

💡 Example 2:

Input: arr1 = [1, 2, 3], arr2 = [4, 4, 4]
Output: 0

Explanation: There is no common prefix for any pair (arr1[i], arr2[j]), so the result is 0.

🐢 Brute-Force Solution

The brute-force approach compares each number in arr1 with each number in arr2 to find the common prefix between them. The process involves the following steps:

1. Convert Numbers to Strings: Convert each number in arr1 and arr2 to a string, as comparing prefixes of digits is easier when treated as strings.
2. Compare Every Pair: For each pair (x, y) from arr1 and arr2, compare the corresponding characters of their string representations.
3. Track Maximum Length: Keep track of the longest common prefix found across all pairs.

🧑‍💻 Brute-Force Code Implementation

def longest_common_prefix_length(arr1, arr2):
    # Function to calculate common prefix length between two strings
    def common_prefix_length(str1, str2):
        length = 0
        for c1, c2 in zip(str1, str2):
            if c1 == c2:
                length += 1
            else:
                break
        return length

    max_len = 0  # Track the maximum common prefix length
    for x in arr1:
        for y in arr2:
            # Convert both numbers to strings and compare
            max_len = max(max_len, common_prefix_length(str(x), str(y)))

    return max_len

# Example usage
arr1 = [1, 10, 100]
arr2 = [1000]
print(longest_common_prefix_length(arr1, arr2))  # Output: 3

🕰️ Time Complexity of Brute-Force:

• O(n * m * k) where n and m are the lengths of arr1 and arr2, and k is the length of the longest number (in terms of digits).
• This approach compares every pair, making it inefficient for large inputs.

⚡ Optimized Solution: Sorting and Two-Pointer Technique

The brute-force approach can be optimized by leveraging sorting and the two-pointer technique. The idea is that once the arrays are sorted (as strings), numbers with common prefixes will be placed close to each other. We can then compare numbers more efficiently.

💡 Optimized Approach:

1. Sort the Arrays: Convert numbers to strings and sort arr1 and arr2 lexicographically.
2. Use Two Pointers: Use two pointers to compare the numbers from the sorted arrays and find the longest common prefix.

🔍 Steps:

• Sort both arr1 and arr2 as strings.
• Use two pointers to scan through both arrays, comparing the closest numbers after sorting.

🚀 Optimized Code Implementation

def longest_common_prefix_length_optimized(arr1, arr2):
    # Function to calculate common prefix length between two strings
    def common_prefix_length(str1, str2):
        length = 0
        for c1, c2 in zip(str1, str2):
            if c1 == c2:
                length += 1
            else:
                break
        return length

    # Convert numbers to strings and sort them
    arr1_str = sorted(map(str, arr1))
    arr2_str = sorted(map(str, arr2))
    
    max_len = 0  # Track the maximum common prefix length
    i, j = 0, 0  # Two pointers for arr1 and arr2
    
    # Compare the closest numbers between the sorted arrays
    while i < len(arr1_str) and j < len(arr2_str):
        # Find the common prefix length between arr1_str[i] and arr2_str[j]
        max_len = max(max_len, common_prefix_length(arr1_str[i], arr2_str[j]))
        
        # Move the pointer that has the smaller number
        if arr1_str[i] < arr2_str[j]:
            i += 1
        else:
            j += 1
    
    return max_len

# Example usage
arr1 = [1, 10, 100]
arr2 = [1000]
print(longest_common_prefix_length_optimized(arr1, arr2))  # Output: 3

⏳ Time Complexity of Optimized Solution:

• O(n log n + m log m) for sorting both arrays, where n and m are the lengths of arr1 and arr2.
• O(n + m) for the two-pointer scan.
• Overall time complexity: O(n log n + m log m), which is significantly faster than the brute-force approach.

📝 Conclusion

🐢 Brute-Force Solution:

• Simple but inefficient, with time complexity O(n * m * k).
• Works for small inputs but becomes slow for large arrays.

⚡ Optimized Solution (Sorting + Two-Pointer):

• Time complexity O(n log n + m log m).
• This approach efficiently reduces unnecessary comparisons by leveraging sorting and the two-pointer technique.

When working with large datasets, the optimized solution is preferable, as it drastically reduces the time complexity compared to the brute-force solution. The key idea here is that sorting brings numbers with similar prefixes closer together, making it easier to find the longest common prefix.