Problem Statement in English

You’re given two arrays of integers. You have to find the length of the longest common prefix between any two integers, one from each array.

Common prefixes from the same array don’t count.

Approach

We can use two hashmaps to store the count of all prefixes in both arrays. Then we can iterate over one hashmap and check if the same prefix exists in the other hashmap. If it does, we can update our result with the length of that prefix.

And we’re done!

Solution in Python


class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        hm1 = defaultdict(int)
        hm2 = defaultdict(int)

        for n in arr1:
            s = str(n)

            for i in range(1, len(s) + 1):
                hm1[s[:i]] += 1
        
        for n in arr2:
            s = str(n)

            for i in range(1, len(s) + 1):
                hm2[s[:i]] += 1

        res = 0
        for k in hm1:
            if hm2[k]:
                res = max(res, len(k))

        return res

Complexity

  • Time: $O(n \cdot m)$

  • Space: $O(n \cdot m)$
    Since we store the prefix counts in two hashmaps. This can be be reduced if instead of string prefixes, we store them as integers.

And we are done.