392. Find the Length of the Longest Common Prefix

Convert each number to a string and compare character by character for every pair across the two arrays, tracking the longest matching prefix.

Approach

1. For every pair (x, y) with x from arr1 and y from arr2:
   • Convert both to strings.
   • Compare characters from the left; count how many match before the first difference.
   • Track the global maximum prefix length.

Complexity

• Time: O(n * m * d) where n, m are array lengths and d is the max number of digits (up to 9). With n, m = 5*10^4, this is up to ~2.25 * 10^9 -- too slow.
• Space: O(d) for the string conversions.

class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        int result = 0;
        for (int x : arr1) {
            for (int y : arr2) {
                String sx = String.valueOf(x);
                String sy = String.valueOf(y);
                int length = 0;
                for (int i = 0; i < Math.min(sx.length(), sy.length()); i++) {
                    if (sx.charAt(i) != sy.charAt(i)) break;
                    length++;
                }
                result = Math.max(result, length);
            }
        }
        return result;
    }
}

Instead of checking every pair, store all digit-prefixes of numbers in arr1 into a set. Then for each number in arr2, check its prefixes from longest to shortest -- the first hit is the best match for that number.

Key insight

A common prefix between two numbers x and y means they share the same leading digits. Rather than comparing every pair, we can pre-compute all possible prefixes from one array, store them in a set, and query from the other.

For example, the number 12345 generates prefixes: "1", "12", "123", "1234", "12345".

Steps

1. Build the prefix set -- iterate through arr1. For each number, convert to string and add every prefix (s[:1], s[:2], ..., s[:len(s)]) to a hash set.
2. Query from arr2 -- for each number in arr2, convert to string and check its prefixes from longest to shortest. The first match gives the longest common prefix for that number.
3. Track the maximum across all numbers in arr2.

Walk-through

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

Step 1 -- Build prefix set from arr1:

Final set: {"1", "10", "100"}

Step 2 -- Query from arr2:

Result: 3.

Why it works

Every prefix of a number is a potential match. By storing them all from arr1 upfront (O(n * d) entries, where d is the max number of digits -- at most 9), each number in arr2 needs at most d lookups instead of scanning all of arr1. This drops the time from O(n * m * d) to O((n + m) * d).

Edge cases

• No common prefix at all: e.g., arr1 = [1, 2, 3], arr2 = [4, 4, 4] -- no prefix from arr2 appears in the set, so the answer is 0.
• Exact match: arr1 = [123], arr2 = [123] -- the full number "123" is in the prefix set, giving length 3.
• Single digit numbers: always match if the same digit appears in both arrays, giving length 1.

Complexity

• Time: O((n + m) * d) where d <= 9 (digits in numbers up to 10^8). Essentially O(n + m).
• Space: O(n * d) for the prefix set. At most 9 * 5 * 10^4 = 4.5 * 10^5 entries.