⚡Flashcard Drill➔
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

  1. Insert every prefix of every number in arr1 into a hash set.
  2. For each number in arr2, extend its prefix character by character and stop as soon as the prefix is not in the set.
  3. Track the maximum matched length across all of arr2.
  4. 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 123 and 12 share 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems