3043. Find the Length of the Longest Common Prefix

Array
Hash Table

TIME

O((n + m) * D), where D is the maximum digit count

SPACE

O(n * D)

Intuition

For any number, repeatedly removing its last digit gives all of its prefixes from longest to shortest.

If we store every prefix that appears in arr1, then for each value in arr2 we can remove digits from the right until we find the longest prefix that also appears in arr1.

Approach

Create a set prefixes.
For every number in arr1, add the number and every value formed by repeatedly dividing it by 10.
For every number in arr2:
- start from the full number
- if it exists in prefixes, update the answer with its digit length and stop checking that number
- otherwise divide by 10 and continue
Return the maximum length found.

Complexity

Let D be the maximum number of digits in any value.

Time: O((n + m) * D)
Space: O(n * D)

Since values are at most 10^8, D is at most 9.

Edge Cases

No common leading digit -> return 0
A full number from arr2 is a prefix from arr1
Common prefix has trailing zeros, such as 100
Multiple values share prefixes -> the set naturally deduplicates them

Code

from typing import List


class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        """
        3043. Find the Length of the Longest Common Prefix
        Time: O((n + m) * D), where D is the maximum digit count
        Space: O(n * D)
        """
        prefixes = set()

        for num in arr1:
            prefix = num
            while prefix > 0:
                prefixes.add(prefix)
                prefix //= 10

        longest = 0
        for num in arr2:
            prefix = num
            while prefix > 0:
                if prefix in prefixes:
                    longest = max(longest, len(str(prefix)))
                    break
                prefix //= 10

        return longest

import java.util.HashSet;
import java.util.Set;

/**
 * 3043. Find the Length of the Longest Common Prefix
 * Time: O((n + m) * D), where D is the maximum digit count
 * Space: O(n * D)
 */
class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Set<Integer> prefixes = new HashSet<>();

        for (int num : arr1) {
            int prefix = num;
            while (prefix > 0) {
                prefixes.add(prefix);
                prefix /= 10;
            }
        }

        int longest = 0;
        for (int num : arr2) {
            int prefix = num;
            while (prefix > 0) {
                if (prefixes.contains(prefix)) {
                    longest = Math.max(longest, digitLength(prefix));
                    break;
                }
                prefix /= 10;
            }
        }

        return longest;
    }

    private int digitLength(int num) {
        int length = 0;
        while (num > 0) {
            length++;
            num /= 10;
        }
        return length;
    }
}