Find the Length of the Longest Common Prefix — Digit Trie

Problem Statement#

LeetCode 3043 — Find the Length of the Longest Common Prefix | Difficulty: Medium

You are given two arrays of positive integers arr1 and arr2.

A prefix of a positive integer is an integer formed by one or more of its digits, starting from its leftmost digit. For example, 123 is a prefix of the integer 12345, while 234 is not.

A common prefix of two integers a and b is an integer c such that c is a prefix of both a and b. For example, 5655359 and 56554 have common prefixes 565 and 5655, while 1223 and 43456 do not have a common prefix.

You need to find the length of the longest common prefix between all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.

Return the length of the longest common prefix among all pairs. If no common prefix exists among them, return 0.

Example:

Input:  arr1 = [1,10,100], arr2 = [1000]
Output: 3
Explanation: 100 is a prefix of 1000 → length 3.

Constraints:

• 1 <= arr1.length, arr2.length <= 5 * 10^4
• 1 <= arr1[i], arr2[i] <= 10^8

Why This Problem Matters#

Find the Length of the Longest Common Prefix is a fresh-feeling 2024 contest problem that quickly entered the FAANG interview rotation at Google, Amazon, and Microsoft. It demonstrates a critical trie idea: the alphabet does not have to be letters. Digits work, bits work, codepoints work, byte-pairs work — anything you can decompose into a sequence becomes a candidate for a trie.

The problem also showcases the asymmetric build-query pattern (build trie from one array, query with the other) — exactly the workflow that powers production prefix-matching services like dictionary autocomplete, search query rewriting, and IP routing tables (LPM trees, which are essentially binary tries over IP bits).

The Core Insight#

We need the longest common prefix length over all pairs (x, y) with x in arr1 and y in arr2. The brute force is O(N times M times D) where D is digit count — too slow at 50,000 × 50,000.

Two-step trie approach:

1. Build phase — convert each number in arr1 to its digit string, insert into a trie. Each node represents a digit 0..9. Total cost O(sum of digits in arr1).
2. Query phase — for each number in arr2, walk the trie digit by digit. The walk length before falling off the trie is the longest common prefix length between this arr2 element and some arr1 element. Track the global maximum.

Why this works: a number y from arr2 walks down the trie matching shared digits. The walk depth equals the length of the longest prefix of y that exists as a prefix of some arr1 value. Maximising over all y gives the answer.

Total complexity: O((N + M) times D) where D ≤ 9 for values up to 10^8. That is at most 9 × 100,000 = 900,000 operations — instant.

Visual Dry Run#

arr1 = [1, 10, 100], arr2 = [1000]. Convert to strings: ["1", "10", "100"] and ["1000"].

Build trie of arr1:

root
 |-- "1" (END "1")
      |-- "0" (END "10")
           |-- "0" (END "100")

Walk "1000" through the trie:

'1' → exists, depth = 1
'0' → exists, depth = 2
'0' → exists, depth = 3
'0' → not in trie (no fourth digit), stop.

Maximum prefix length = 3. Answer = 3.

If we had instead arr2 = [123, 456]:

• Walk "123": '1' exists (depth 1), '2' not in trie → stop at 1.
• Walk "456": '4' not in trie → depth 0.

Maximum across all arr2 walks = 1.

Solution (Optimal) — Digit Trie#

Python#

class TrieNode:
    __slots__ = ("children",)
    def __init__(self):
        self.children = {}
 
class Solution:
    def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int:
        root = TrieNode()
        # Build phase
        for n in arr1:
            node = root
            for ch in str(n):
                if ch not in node.children:
                    node.children[ch] = TrieNode()
                node = node.children[ch]
        # Query phase
        ans = 0
        for n in arr2:
            node = root
            depth = 0
            for ch in str(n):
                if ch not in node.children:
                    break
                node = node.children[ch]
                depth += 1
            if depth > ans:
                ans = depth
        return ans

JavaScript#

class TrieNode {
  constructor() {
    this.children = {};
  }
}
 
var longestCommonPrefix = function(arr1, arr2) {
  const root = new TrieNode();
  for (const n of arr1) {
    let node = root;
    for (const ch of String(n)) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
  }
  let ans = 0;
  for (const n of arr2) {
    let node = root, depth = 0;
    for (const ch of String(n)) {
      if (!node.children[ch]) break;
      node = node.children[ch];
      depth++;
    }
    if (depth > ans) ans = depth;
  }
  return ans;
};

Complexity#

• Time: O((N + M) times D) where D ≤ 9 for values ≤ 10^8.
• Space: O(sum of digits in arr1) for the trie.

Common Mistakes#

1. Building tries on both arrays then intersecting — works but doubles memory. The asymmetric build-query approach is enough.
2. Comparing every pair (x, y) directly — O(N times M times D) and TLEs at 5 × 10^4 each side.
3. Treating numbers as integers and using // 10 to extract digits — works but iterates from least-significant digit; the trie needs most-significant first.
4. Forgetting that the answer can be 0 — initialise ans = 0, not -1 or None.
5. Using the smaller array for build instead of the larger — pick whichever is smaller for slightly less memory; functionally either works.
6. Reading "common prefix of two integers" as "shared digits anywhere" — common prefix means leading characters of the decimal representation, not subsequence.

Interview Tips#

• Open with the brute force pair-by-pair, state its O(N times M times D) cost, and note it TLEs.
• Pitch the digit trie: "We are doing N times M prefix-match queries; that is exactly what a trie accelerates."
• Justify "build from arr1, query with arr2" — the trie holds all arr1 prefixes; each arr2 walk reveals the best match.
• Mention that the alphabet of the trie can be anything — digits in this case. This shows you understand the abstraction.
• Note that we never need to mark "end of word" — we are doing prefix matching, not exact lookup.

Follow-up Questions#

• What if arrays contain negative numbers? Skip the sign or insert it as a separate edge; the algorithm extends.
• Find the actual longest common prefix string, not just length? Track the prefix during the walk; return on the longest match.
• Find longest common prefix among k arrays? Build trie from union, walk with each array; track depth where all k contributed.
• Streaming arr2 against fixed arr1? Trie is already built; each query is O(D).
• What if arr1 is huge and memory-bound? Compress to a Patricia (radix) trie or use ternary search trees.

Key Takeaways#

• Tries are not just for letters — digits, bits, byte-pairs, codepoints all work as alphabets.
• Build the trie from one array; query with the other in O(D) per number.
• Total complexity O((N + M) times D); for D ≤ 9 this is effectively linear.
• Track the maximum walk depth across all arr2 numbers — that is the longest common prefix length.
• No need for end-of-word markers when doing prefix matching only.
• This pattern — asymmetric build-query trie — powers IP routing (LPM), DNS suffix matching, and search-query rewriting.