Find the Length of the Longest Common Prefix
Problem
You are given two arrays of positive integers, arr1 and arr2. A common prefix of two numbers is a number formed by leading digits they share when written in decimal — for example, 565 and 5655 share the prefix 565. Considering every pair (x, y) with x from arr1 and y from arr2, return the number of digits in the longest common prefix among all pairs, or 0 if no pair shares even a first digit.
arr1 = [1, 10, 100], arr2 = [1000]3def longest_common_prefix(arr1, arr2):
trie = {}
for a in arr1:
node = trie
for d in str(a):
node = node.setdefault(d, {})
best = 0
for b in arr2:
node = trie
length = 0
for d in str(b):
if d not in node:
break
node = node[d]
length += 1
best = max(best, length)
return bestfunction longestCommonPrefix(arr1, arr2) {
const trie = {};
for (const a of arr1) {
let node = trie;
for (const d of String(a)) {
node = node[d] || (node[d] = {});
}
}
let best = 0;
for (const b of arr2) {
let node = trie, len = 0;
for (const d of String(b)) {
if (!(d in node)) break;
node = node[d];
len++;
}
best = Math.max(best, len);
}
return best;
}int longestCommonPrefix(int[] arr1, int[] arr2) {
Map<Character, Object> trie = new HashMap<>();
for (int a : arr1) {
Map<Character, Object> node = trie;
for (char d : String.valueOf(a).toCharArray()) {
node = (Map<Character, Object>) node.computeIfAbsent(d, k -> new HashMap<>());
}
}
int best = 0;
for (int b : arr2) {
Map<Character, Object> node = trie;
int len = 0;
for (char d : String.valueOf(b).toCharArray()) {
if (!node.containsKey(d)) break;
node = (Map<Character, Object>) node.get(d);
len++;
}
best = Math.max(best, len);
}
return best;
}struct Node { Node* next[10] = {}; };
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
Node* trie = new Node();
for (int a : arr1) {
Node* node = trie;
for (char d : to_string(a)) {
int i = d - '0';
if (!node->next[i]) node->next[i] = new Node();
node = node->next[i];
}
}
int best = 0;
for (int b : arr2) {
Node* node = trie;
int len = 0;
for (char d : to_string(b)) {
int i = d - '0';
if (!node->next[i]) break;
node = node->next[i];
len++;
}
best = max(best, len);
}
return best;
}Explanation
Comparing every pair directly is far too slow when each array can hold 5·10⁴ numbers. The key insight is that a common prefix of two numbers is just a shared path of leading digits — exactly the thing a trie encodes. If all prefixes of arr1 live in a trie, then "the longest prefix this arr2 number shares with any arr1 number" is a single downward walk.
Build phase: each number of arr1 is inserted digit by digit with node.setdefault(d, {}). Every node created along the way represents one prefix, so [1, 10, 100] produces the chain 1 → 0 → 0 whose three nodes are the prefixes 1, 10 and 100.
Probe phase: for each number of arr2, walk from the root and follow matching digit children. Each successful step means one more shared leading digit, so the depth reached is the longest common prefix between this number and the best-matching arr1 number. We keep the maximum depth over all probes in best.
Default example: probing 1000 in the trie of [1, 10, 100] matches digits 1, 0, 0 (depth 3), then the fourth digit 0 has no child, so the walk stops. The longest common prefix is "100" and the answer is 3.
Each number has at most D ≈ 9 digits (values are below 10⁹), so building the trie costs O(n·D), probing costs O(m·D), and no pair-by-pair comparison ever happens. The trie stores at most one node per inserted digit, giving O(n·D) space.