NeetCode #155LC-3043MediumArrays & Hashing
← Back to All Problems#155 · #3043 · Find the Length of the Longest Common Prefix(最长公共前缀的长度)
📌 Problem Statement & Constraints
You are given two arrays of positive integers
arr1 and arr2. For each pair of integers, consider their decimal string representations. Return the length of the longest common prefix among all such pairs. Constraints: 1 <= arr1.length, arr2.length <= 5 * 10^4, 1 <= arr1[i], arr2[i] <= 10^8.💡 Core Algorithmic Approaches
- Insert every prefix of every number in
arr1into a hash set. - For each number in
arr2, extend its prefix character by character and stop as soon as the prefix is not in the set. - Track the maximum matched length across all of
arr2. - The early break matters: once a prefix fails, every longer prefix also fails.
💻 Benchmark Python3 Implementation
class Solution:
def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
prefixes = set()
for x in arr1:
s = str(x)
for i in range(1, len(s) + 1):
prefixes.add(s[:i]) # every prefix of every number
res = 0
for x in arr2:
s = str(x)
for i in range(1, len(s) + 1):
if s[:i] in prefixes:
res = max(res, i)
else:
break # longer prefixes cannot match either
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O((n + m) * L) where L is the maximum number of digits (9 here), since each prefix is inserted or looked up once.
💾 Space Complexity
O(n * L) for the prefix set.
⚠️ Interview Pitfalls & Follow-ups
- Comparing numbers numerically: the problem is about the decimal string prefix, so
123and12share the prefix"12"of length 2, not the numeric prefix. - Forgetting the early break: it is not required for correctness but avoids pointless lookups.
- Storing full numbers instead of prefixes: the lookup would then require checking all possible prefix lengths anyway, defeating the purpose.
- Using a trie: also correct and O(n * L) in both time and space, but more code than the prefix-set approach for the small L here.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.