LCP of Arrays LeetCode 3043 Guide

LeetCode 3043 Find the Length of the Longest Common Prefix gives you two arrays of positive integers, arr1 and arr2. For any pair of integers — one chosen from arr1, one from arr2 — a common prefix is defined as a shared sequence of leading digits. For example, 123 and 125 share the prefix "12" of length 2, and 456 and 4 share the prefix "4" of length 1. Your task is to find the maximum such prefix length across all possible pairs.

The prefix here is a numeric prefix, not a string-sort prefix. You are comparing the most-significant digits of two integers, left to right, until the digits diverge. The integer 9 has a single-digit prefix "9"; the integer 987 has prefixes "9", "98", and "987". If no pair shares even a single leading digit, the answer is 0.

The constraints allow arr1 and arr2 each to have up to 10^5 elements, with each integer up to 10^8 — so at most 9 digits each. A brute-force O(n × m × d) approach checking all pairs is too slow. The optimal approach is O((n + m) × d) using a trie or a HashSet of all prefixes from one array, where d is the max digit length (at most 9).

The trie approach treats each integer as a string of its decimal digits and inserts all numbers from arr1 into a digit trie — a tree where each node has up to 10 children (digits 0–9). After building the trie, you query each number in arr2 by traversing the trie digit by digit from the most-significant digit. You stop as soon as a digit in the query number has no corresponding child in the trie, and record how many digits matched so far.

After querying all numbers in arr2, the maximum recorded match length is the answer. The trie efficiently encodes all prefix information from arr1: any path from the root to a node represents a prefix that appears in at least one number from arr1. Querying arr2 through this structure finds the longest shared prefix in a single traversal per query number.

The trie approach achieves O(n × d + m × d) time — O(n × d) to build and O(m × d) to query — where n = |arr1|, m = |arr2|, and d is the maximum digit count (≤ 9 for values up to 10^8). Space is O(n × d) for the trie nodes in the worst case.

To build the trie, iterate through every number in arr1. Convert each number to its decimal string representation. Then walk the string character by character (digit by digit), starting from the most-significant digit. At each position, look up the digit in the current node's children dictionary. If the child does not exist, create a new trie node and add it. Then move to the child and continue to the next digit.

No end marker or "is_end" flag is needed in this problem. Unlike a word search trie where you need to know which nodes terminate valid words, here you only care about prefix length — how far a query can travel down the trie. The depth of the traversal is the matched prefix length. The structure of the trie itself encodes all prefix information; every node that exists represents a prefix that appears in arr1.

The trie is implemented with a dictionary of children at each node, keyed by digit character ('0'–'9'). A simple Python class or a plain dict-of-dict construction both work. For Java, an array of size 10 at each node is faster than a HashMap. The root node is an empty node with no parent; depth 0 corresponds to the root and depth k corresponds to having matched k digits.

To query, iterate through every number in arr2. Convert each number to its decimal string. Start at the trie root and walk digit by digit. At each step, check if the current digit character exists as a child of the current node. If yes, move to the child and increment the match counter. If no, stop — the current digit has no match in any arr1 number prefix, so the traversal ends.

After the traversal for one arr2 number, update the global maximum with the current match counter. Reset the counter to 0 and the current node back to root for the next arr2 number. After all arr2 numbers are queried, return the global maximum. If the maximum is still 0, no pair shares a leading digit.

The query is naturally bounded: it runs at most d steps (the number of digits in the arr2 number) before either exhausting the number or hitting a missing child. This guarantees O(d) per query. The total query cost is O(m × d), which combined with the O(n × d) build cost gives O((n + m) × d) overall.

The HashSet approach avoids implementing a trie by explicitly materializing all prefixes of every arr1 number into a set. For a number like 1234, you add "1", "12", "123", and "1234" to the set. For a number with d digits, this generates d prefix strings. After processing all arr1 numbers, the set contains every prefix that appears in arr1.

To answer a query for an arr2 number, generate all its prefixes in order from shortest to longest and check each against the set. Record the length of the longest prefix string found in the set. Because you check from shortest to longest, you can scan all and take the max, or scan from longest to shortest and return early on the first hit — either is correct.

The HashSet approach is simpler to code in an interview setting: no custom data structure required, just a set and string slicing. The tradeoff is memory: you store up to n × d prefix strings, each of length up to d, for O(n × d^2) total character storage versus the trie's O(n × d) nodes. For d ≤ 9, this is at most 9x more character storage — acceptable but not ideal for very large inputs.

Python trie solution: class TrieNode: def __init__(self): self.children = {}. Build: root = TrieNode(); for num in arr1: node = root; for ch in str(num): if ch not in node.children: node.children[ch] = TrieNode(); node = node.children[ch]. Query: ans = 0; for num in arr2: node = root; length = 0; for ch in str(num): if ch not in node.children: break; node = node.children[ch]; length += 1; ans = max(ans, length). Return ans. O(sum of digits of arr1 + arr2) time, O(sum of digits of arr1) space.

Python HashSet alternative (often preferred in interviews for brevity): prefix_set = set(); for num in arr1: s = str(num); [prefix_set.add(s[:i]) for i in range(1, len(s)+1)]; ans = 0; for num in arr2: t = str(num); ans = max(ans, max((i for i in range(1, len(t)+1) if t[:i] in prefix_set), default=0)); return ans.

Java trie solution: define a TrieNode class with int[] children = new int[10] (index-based adjacency array). Insert each arr1 number as a string into the trie. Query each arr2 number, advancing through children by digit. Java's Integer.toString() converts ints to decimal strings. Both build and query loops run in O(d) per number. The index-based trie avoids HashMap overhead.

Implement Trie (LeetCode 208) is the foundational problem: build a trie supporting insert, search, and startsWith operations on lowercase strings. Mastering this problem gives you the TrieNode class template used in almost every trie problem. LCP 3043 is a direct application: build the trie and use startsWith-style traversal to measure match depth.

Implement Trie II (LeetCode 1804, prefix count variant) extends the basic trie with a count of how many words pass through each node. This is useful when you need to know not just whether a prefix exists but how many words share it — a common follow-up to this problem and a useful component in more advanced trie applications.

Longest Common Prefix of an array of strings (LeetCode 14) is the string analogue of this problem. While that problem is solvable with sorting or character-by-character scanning, a trie approach also works and generalizes naturally to the integer-array version (LeetCode 3043). Related problems using tries include Word Search II (212), Design Search Autocomplete (642), and the broader family of prefix-tree problems on arrays, integers, and binary representations.