How to Solve Find the Length of the Longest Common Prefix

Start by generating all prefixes of integers in arr1 and store them in a HashSet for O(1) lookup. Then, iterate over arr2, checking each prefix against the HashSet and tracking the maximum prefix length. This ensures the solution leverages the array scanning plus hash lookup pattern, avoiding unnecessary pairwise comparisons and reducing runtime complexity.

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

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.

How GhostInterview Helps

• Automatically generates all prefixes of arr1 and arr2 and tracks maximum length efficiently.
• Highlights the exact array scanning plus hash lookup pattern to avoid TLE mistakes.
• Provides step-by-step matching logic for each arr2 element against the HashSet.

Topic Pages

• Array
• Hash Table
• String
• Trie

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.