#3043

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find the Length of the Longest Common Prefix

Determine the length of the longest common prefix between two integer arrays using array scanning and hash lookup efficiently.

array hash table string trie

Problem Statement

Given two arrays of positive integers arr1 and arr2, identify the length of the longest integer prefix common to at least one element from each array. A prefix of an integer is any sequence of its starting digits, for example, 123 is a prefix of 12345, while 234 is not.

A common prefix of integers a and b is an integer c that is a prefix of both a and b. For example, 5655359 and 56554 share common prefixes 565 and 5655. Return the length of the longest such common prefix across all pairs from arr1 and arr2.

Examples

Example 1

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

Output: 3

There are 3 pairs (arr1[i], arr2[j]):

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. The longest common prefix is 100 with a length of 3.

Example 2

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

Output: 0

There exists no common prefix for any pair (arr1[i], arr2[j]), hence we return 0. Note that common prefixes between elements of the same array do not count.

Constraints

1 <= arr1.length, arr2.length <= 5 * 104
1 <= arr1[i], arr2[i] <= 108

Solution Approach

Generate Prefixes with HashSet

Iterate over arr1 and create all possible prefixes for each integer. Insert each prefix into a HashSet to allow constant-time lookup when scanning arr2. This ensures the array scanning plus hash lookup pattern is applied correctly.

Scan arr2 for Matches

For each integer in arr2, generate its prefixes and check against the HashSet. Track the length of matching prefixes and update the maximum length found. Avoid redundant checks by stopping at the first mismatch.

Return Maximum Length

After scanning all elements in arr2, return the maximum prefix length found. If no common prefix exists, return 0. This final step consolidates the result from the hash lookup checks efficiently.

Complexity Analysis

Metric	Value
Time	O(m \cdot d + n \cdot d) = O(m + n)
Space	O(m \cdot d) = O(m)

Time complexity is O(m * d + n * d) where m and n are array sizes and d is the maximum digit length, effectively O(m + n) due to constant prefix generation. Space complexity is O(m * d) for storing all arr1 prefixes in the HashSet.

What Interviewers Usually Probe

Ask candidates about generating prefixes efficiently without pairwise comparison.
Probe knowledge of HashSet lookup and why it reduces complexity.
Check understanding of integer prefix handling and array scanning trade-offs.

Common Pitfalls or Variants

Common pitfalls

Failing to stop prefix comparison at the first mismatch leading to wrong lengths.
Using nested loops for all pairs instead of HashSet, causing TLE on large arrays.
Ignoring single-digit or full-length prefixes, missing edge cases.

Follow-up variants

Find the longest common prefix among multiple arrays instead of two.
Return the actual longest common prefix value rather than just the length.
Apply the prefix check to strings instead of integers, maintaining the hash lookup pattern.

FAQ

What is the fastest way to find the longest common prefix between two integer arrays?

Use array scanning plus hash lookup by generating all prefixes of arr1 in a HashSet and checking each arr2 element's prefixes against it.

Does this approach work for very large arrays?

Yes, because storing prefixes in a HashSet avoids O(m*n) comparisons and scales linearly with the number of elements and digit lengths.

How do we handle integers with different digit lengths?

Generate prefixes up to the length of each integer and compare; the HashSet handles varying prefix lengths automatically.

What should be returned if no common prefix exists?

Return 0, indicating no prefix is shared between any elements of arr1 and arr2.

Can this method be adapted for the problem 'Find the Length of the Longest Common Prefix' with strings?

Yes, the same array scanning plus hash lookup pattern works by treating string prefixes instead of integer prefixes.

terminal

Solution

Solution 1: Hash Table

We can use a hash table to store all the prefixes of the numbers in `arr1`. Then, we traverse all the numbers $x$ in `arr2`. For each number $x$, we start from the highest bit and gradually decrease, checking whether it exists in the hash table. If it does, we have found a common prefix, and we can update the answer accordingly.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        s = set()
        for x in arr1:
            while x:
                s.add(x)
                x //= 10
        ans = 0
        for x in arr2:
            while x:
                if x in s:
                    ans = max(ans, len(str(x)))
                    break
                x //= 10
        return ans

Continue Practicing

#3076 shortest uncommon substring in an array #2707 extra characters in a string #2227 encrypt and decrypt strings