Practice/Apple/Leetcode 3043. Find the Length of the Longest Common Prefix

Leetcode 3043. Find the Length of the Longest Common Prefix

CodingOptional

Problem

You are given two arrays of positive integers. Your task is to find the maximum length of a common prefix when comparing the digit sequences of numbers from the first array with numbers from the second array.

A common prefix means that when you write both numbers as strings of digits, they start with the same sequence of digits reading from left to right. For example, the numbers 1234 and 1289 share a common prefix "12" of length 2.

Return the length of the longest such prefix found between any pair of numbers (one from each array). If no common prefix exists, return 0.

Requirements

1. Compare every number from the first array with every number from the second array
2. For each pair, determine the length of their shared prefix (starting from the leftmost digit)
3. Return the maximum prefix length found across all pairs
4. If no numbers share any common starting digits, return 0

Constraints

• 1 ≤ arr1.length, arr2.length ≤ 50,000
• 1 ≤ arr1[i], arr2[j] ≤ 10^8
• All numbers are positive integers
• Time complexity should be better than O(n × m × d) where n and m are array lengths and d is average digit count

Examples

Example 1:

Input: arr1 = [123, 456, 789], arr2 = [120, 340, 800] Output: 2 Explanation: The number 123 from arr1 and 120 from arr2 share the prefix "12" which has length 2. This is the longest common prefix among all pairs.

Example 2:

Input: arr1 = [1, 2, 3], arr2 = [4, 5, 6] Output: 0 Explanation: No number from arr1 shares any starting digit with any number from arr2.

Example 3:

Input: arr1 = [1000, 2000], arr2 = [10000, 20000] Output: 4 Explanation: 1000 and 10000 share the prefix "1000" with length 4. Similarly, 2000 and 20000 share "2000" with length 4.