Find the Length of the Longest Common Prefix solution and explanation
Google
9 more videos on this problem
Find the Length of the Longest Common Prefix | 2 Approaches | Leetcode 3043 | codestorywithMIKcodestorywithMIK · 37:07 · 20K views
Find the Length of the Longest Common Prefix - Leetcode 3043 - PythonNeetCodeIO · 15:49 · 16K views
3043. Find the Length of the Longest Common Prefix | Tries | Leetcode Daily Challenge | DSA | JavaShashCode · 18:51 · 2K views
Find the Length of the Longest Common Prefix | Leetcode 3043Techdose · 13:11 · 2K views
3043. Find the Length of the Longest Common Prefix (Leetcode Medium)Programming Live with Larry · 5:58 · 694 views
3043. Find the Length of the Longest Common Prefix | Leetcode Daily - PythonLeetcode Daily · 7:46 · 306 views
3043. Find the Length of the Longest Common Prefix | Leetcode Daily Challenge| Trie | HashSet |LeetCodeWithMonu · 14:43 · 199 views
Find the Length of the Longest Common Prefix | LeetCode 3043 | HashSet | TrieStreak To Scale · 4:13 · 107 views
3043. Find the Length of the Longest Common Prefix | C++ | Simple and detailed explanation |LeetcodeAnshul Explains · 10:17 · 93 views
Leetcode 3043. Find the Length of the Longest Common PrefixExpertFunda · 16:19 · 69 views
The problem
You are given two arrays with 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 1:
Input: arr1 = [1,10,100], arr2 = [1000] Output: 3 Explanation: There are 3 pairs (arr1[i], arr2[j]): - The longest common prefix of (1, 1000) is 1. - The longest common prefix of (10, 1000) is 10. - The longest common prefix of (100, 1000) is 100. The longest common prefix is 100 with a length of 3.
Example 2:
Input: arr1 = [1,2,3], arr2 = [4,4,4] Output: 0 Explanation: There exists no common prefix for any pair (arr1[i], arr2[j]), hence we return 0. Note that common prefixes between elements of the same array do not count.
Constraints:
1 <= arr1.length, arr2.length <= 5 * 1041 <= arr1[i], arr2[i] <= 108
Approach overview
Problem Overview: Given two integer arrays, the task is to determine the maximum length of a shared prefix between any number from the first array and any number from the second array. Treat each number as a string and compare their leading digits to find the longest matching prefix.
Approach 1: Brute Force Prefix Comparison (Time: O(n * m * L), Space: O(1))
Convert each number in both arrays to strings. For every pair (a, b) where a comes from the first array and b comes from the second, compare characters from left to right until the prefix breaks. Track the longest matching length encountered. The algorithm performs nested iteration across both arrays and direct character comparison, making it simple but expensive when arrays are large.
This method works well for understanding the core idea of prefix matching. However, the nested comparisons lead to quadratic pair checks. When arrays grow into thousands of elements, the runtime becomes noticeable.
Approach 2: Optimized String Comparison Using Sorting (Time: O((n + m) log(n + m) * L), Space: O(n + m))
Convert every number from both arrays into strings and place them into a combined structure while preserving their origin. Sort the strings lexicographically. In sorted order, strings with similar prefixes naturally appear next to each other. You only need to compare adjacent strings that originate from different arrays and compute their common prefix length.
The key insight is that lexicographic sorting groups similar prefixes together. Instead of checking every possible pair, you reduce comparisons to neighboring strings. Each comparison scans characters until the prefix mismatch occurs. This drastically reduces redundant checks while leveraging efficient sorting behavior.
This approach uses ideas from string ordering and structured comparisons across array elements. A more advanced alternative could use a Trie to store prefixes, but sorting keeps implementation simpler while remaining efficient.
Recommended for interviews: Start by describing the brute force pair comparison to demonstrate understanding of the prefix concept. Then move to the optimized sorting approach. Interviewers typically expect you to reduce unnecessary pair checks and leverage lexicographic ordering, which shows stronger algorithmic reasoning and practical optimization skills.
Approach 1: Brute Force Approach
The simplest way to solve this problem is to iterate over each pair of integers from arr1 and arr2. For each pair, convert the integers to strings and compare character by character to find the common prefix. Keep a running maximum of the lengths of these prefixes.
Since we are comparing each pair, the time complexity is O(n * m * k), where n is the length of arr1, m is the length of arr2, and k is the length of the longest number when converted to a string. Space complexity is O(1) as we're only storing a few additional variables.
def common_prefix_length(a: str, b: str) -> int:
i = 0
while i < len(a) and i < len(b) and a[i] == b[i]:
i += 1
return i
def longest_common_prefix(arr1, arr2):
max_length = 0
for num1 in arr1:
for num2 in arr2:
str1 = str(num1)
str2 = str(num2)
curr_length = common_prefix_length(str1, str2)
max_length = max(max_length, curr_length)
return max_length
arr1 = [1, 10, 100]
arr2 = [1000]
print(longest_common_prefix(arr1, arr2))public class LongestCommonPrefix {
public static int commonPrefixLength(String a, String b) {
int i = 0;
while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) {
i++;
}
return i;
}
public static int longestCommonPrefix(int[] arr1, int[] arr2) {
int maxLength = 0;
for (int num1 : arr1) {
for (int num2 : arr2) {
String str1 = Integer.toString(num1);
String str2 = Integer.toString(num2);
int currLength = commonPrefixLength(str1, str2);
maxLength = Math.max(maxLength, currLength);
}
}
return maxLength;
}
public static void main(String[] args) {
int[] arr1 = {1, 10, 100};
int[] arr2 = {1000};
System.out.println(longestCommonPrefix(arr1, arr2));
}
}#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int commonPrefixLength(const string& a, const string& b) {
int length = 0;
while (length < a.size() && length < b.size() && a[length] == b[length]) {
length++;
}
return length;
}
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
int maxPrefix = 0;
for (const int& num1 : arr1) {
for (const int& num2 : arr2) {
maxPrefix = max(maxPrefix, commonPrefixLength(to_string(num1), to_string(num2)));
}
}
return maxPrefix;
}
int main() {
vector<int> arr1 = {1, 10, 100};
vector<int> arr2 = {1000};
cout << longestCommonPrefix(arr1, arr2) << endl;
return 0;
}function commonPrefixLength(a, b) {
let i = 0;
while (i < a.length && i < b.length && a[i] === b[i]) {
i++;
}
return i;
}
function longestCommonPrefix(arr1, arr2) {
let maxLength = 0;
for (const num1 of arr1) {
for (const num2 of arr2) {
const str1 = num1.toString();
const str2 = num2.toString();
const currLength = commonPrefixLength(str1, str2);
maxLength = Math.max(maxLength, currLength);
}
}
return maxLength;
}
const arr1 = [1, 10, 100];
const arr2 = [1000];
console.log(longestCommonPrefix(arr1, arr2));#include <stdio.h>
#include <string.h>
int commonPrefixLength(char *a, char *b) {
int i = 0;
while (a[i] && b[i] && a[i] == b[i]) {
i++;
}
return i;
}
int longestCommonPrefix(int* arr1, int arr1Size, int* arr2, int arr2Size) {
int maxLength = 0;
for (int i = 0; i < arr1Size; i++) {
for (int j = 0; j < arr2Size; j++) {
char str1[10], str2[10];
sprintf(str1, "%d", arr1[i]);
sprintf(str2, "%d", arr2[j]);
int currLength = commonPrefixLength(str1, str2);
if (currLength > maxLength) {
maxLength = currLength;
}
}
}
return maxLength;
}
int main() {
int arr1[] = {1, 10, 100};
int arr2[] = {1000};
printf("%d\n", longestCommonPrefix(arr1, 3, arr2, 1));
return 0;
}using System;
class Program {
public static int CommonPrefixLength(string a, string b) {
int i = 0;
while (i < a.Length && i < b.Length && a[i] == b[i]) {
i++;
}
return i;
}
public static int LongestCommonPrefix(int[] arr1, int[] arr2) {
int maxLength = 0;
foreach(var num1 in arr1) {
foreach(var num2 in arr2) {
string str1 = num1.ToString();
string str2 = num2.ToString();
int currLength = CommonPrefixLength(str1, str2);
maxLength = Math.Max(maxLength, currLength);
}
}
return maxLength;
}
static void Main() {
int[] arr1 = {1, 10, 100};
int[] arr2 = {1000};
Console.WriteLine(LongestCommonPrefix(arr1, arr2));
}
}This Python solution iterates through each pair of integers from the input arrays, converting them to strings for prefix comparison. It keeps track of and returns the length of the longest common prefix found.
Time complexity: O(n * m * k), Space complexity: O(1)
Approach 2: Optimized String Comparison Approach Using Sorting
This optimized approach leverages sorting of the input arrays to reduce comparisons. After sorting, only consecutive elements can potentially have a longer common prefix with elements of the other array than already found max. This minimizes the number of comparisons, improving efficiency over the brute force approach.
Time complexity may approach O(n + m) in the best-case scenario where common prefixes are found early, but in the worst case it remains approximately O(n * m). The space complexity is still O(1).
def common_prefix_length(a: str, b: str) -> int:
i = 0
while i < len(a) and i < len(b) and a[i] == b[i]:
i += 1
return i
def longest_common_prefix(arr1, arr2):
arr1.sort()
arr2.sort()
max_length = 0
for num1 in arr1:
for num2 in arr2:
curr_length = common_prefix_length(str(num1), str(num2))
max_length = max(max_length, curr_length)
return max_length
arr1 = [1, 10, 100]
arr2 = [1000]
print(longest_common_prefix(arr1, arr2))import java.util.*;
public class LongestCommonPrefix {
public static int commonPrefixLength(String a, String b) {
int i = 0;
while (i < a.length() && i < b.length() && a.charAt(i) == b.charAt(i)) {
i++;
}
return i;
}
public static int longestCommonPrefix(int[] arr1, int[] arr2) {
Arrays.sort(arr1);
Arrays.sort(arr2);
int maxLength = 0;
for (int num1 : arr1) {
for (int num2 : arr2) {
int currLength = commonPrefixLength(Integer.toString(num1), Integer.toString(num2));
maxLength = Math.max(maxLength, currLength);
}
}
return maxLength;
}
public static void main(String[] args) {
int[] arr1 = {1, 10, 100};
int[] arr2 = {1000};
System.out.println(longestCommonPrefix(arr1, arr2));
}
}#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int commonPrefixLength(const string& a, const string& b) {
int length = 0;
while (length < a.size() && length < b.size() && a[length] == b[length]) {
length++;
}
return length;
}
int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
sort(arr1.begin(), arr1.end());
sort(arr2.begin(), arr2.end());
int maxLength = 0;
for (const int& num1 : arr1) {
for (const int& num2 : arr2) {
maxLength = max(maxLength, commonPrefixLength(to_string(num1), to_string(num2)));
}
}
return maxLength;
}
int main() {
vector<int> arr1 = {1, 10, 100};
vector<int> arr2 = {1000};
cout << longestCommonPrefix(arr1, arr2) << endl;
return 0;
}function commonPrefixLength(a, b) {
let i = 0;
while (i < a.length && i < b.length && a[i] === b[i]) {
i++;
}
return i;
}
function longestCommonPrefix(arr1, arr2) {
arr1.sort((a, b) => a - b);
arr2.sort((a, b) => a - b);
let maxLength = 0;
for (const num1 of arr1) {
for (const num2 of arr2) {
const currLength = commonPrefixLength(num1.toString(), num2.toString());
maxLength = Math.max(maxLength, currLength);
}
}
return maxLength;
}
const arr1 = [1, 10, 100];
const arr2 = [1000];
console.log(longestCommonPrefix(arr1, arr2));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int commonPrefixLength(char *a, char *b) {
int i = 0;
while (a[i] && b[i] && a[i] == b[i]) {
i++;
}
return i;
}
int longestCommonPrefix(int* arr1, int arr1Size, int* arr2, int arr2Size) {
qsort(arr1, arr1Size, sizeof(int), compare);
qsort(arr2, arr2Size, sizeof(int), compare);
int maxLength = 0;
for (int i = 0; i < arr1Size; i++) {
for (int j = 0; j < arr2Size; j++) {
char str1[10], str2[10];
sprintf(str1, "%d", arr1[i]);
sprintf(str2, "%d", arr2[j]);
int currLength = commonPrefixLength(str1, str2);
if (currLength > maxLength) {
maxLength = currLength;
}
}
}
return maxLength;
}
int main() {
int arr1[] = {1, 10, 100};
int arr2[] = {1000};
printf("%d\n", longestCommonPrefix(arr1, 3, arr2, 1));
return 0;
}using System;
using System.Linq;
class Program {
public static int CommonPrefixLength(string a, string b) {
int i = 0;
while (i < a.Length && i < b.Length && a[i] == b[i]) {
i++;
}
return i;
}
public static int LongestCommonPrefix(int[] arr1, int[] arr2) {
Array.Sort(arr1);
Array.Sort(arr2);
int maxLength = 0;
foreach(var num1 in arr1) {
foreach(var num2 in arr2) {
int currLength = CommonPrefixLength(num1.ToString(), num2.ToString());
maxLength = Math.Max(maxLength, currLength);
}
}
return maxLength;
}
static void Main() {
int[] arr1 = {1, 10, 100};
int[] arr2 = {1000};
Console.WriteLine(LongestCommonPrefix(arr1, arr2));
}
}This Python solution features sorting of input arrays for efficient prefix checks. Only necessary comparisons are executed, speeding up computation relative to the unsorted method.
Average Time complexity: O(n log n + m log m + n + m), Space complexity: O(1)
Approach 3: Hash Table
We can use a hash table to store all the prefixes of the numbers in arr1. Then, we traverse all the numbers x in arr2. For each number x, we start from the highest bit and gradually decrease, checking whether it exists in the hash table. If it does, we have found a common prefix, and we can update the answer accordingly.
The time complexity is O(m times log M + n times log N), and the space complexity is O(m times log M). Here, m and n are the lengths of arr1 and arr2 respectively, and M and N are the maximum values in arr1 and arr2 respectively.
function longestCommonPrefix(arr1: number[], arr2: number[]): number {
const s: Set<number> = new Set<number>();
for (let x of arr1) {
for (; x; x = Math.floor(x / 10)) {
s.add(x);
}
}
let ans: number = 0;
for (let x of arr2) {
for (; x; x = Math.floor(x / 10)) {
if (s.has(x)) {
ans = Math.max(ans, Math.floor(Math.log10(x)) + 1);
}
}
}
return ans;
}func longestCommonPrefix(arr1 []int, arr2 []int) (ans int) {
s := map[int]bool{}
for _, x := range arr1 {
for ; x > 0; x /= 10 {
s[x] = true
}
}
for _, x := range arr2 {
for ; x > 0; x /= 10 {
if s[x] {
ans = max(ans, int(math.Log10(float64(x)))+1)
break
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time complexity: O(n * m * k), Space complexity: O(1) |
| Optimized String Comparison Approach Using Sorting | Average Time complexity: O(n log n + m log m + n + m), Space complexity: O(1) |
| Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Comparison | O(n * m * L) | O(1) | Small input sizes or when explaining the base idea in interviews |
| Optimized String Comparison Using Sorting | O((n + m) log(n + m) * L) | O(n + m) | General case with larger arrays where reducing pair comparisons improves performance |
Frequently asked questions
Is Find the Length of the Longest Common Prefix easy or hard?
The problem is rated Medium because the brute force idea is simple but inefficient. The challenge lies in recognizing that sorting or Trie-based prefix grouping can drastically reduce comparisons and improve performance.
Find the Length of the Longest Common Prefix Python/Java solution
Typical implementations convert integers to strings and compare prefixes either through brute force pair checking or by sorting and comparing adjacent strings. Both Python and Java solutions rely on character-by-character prefix comparison and standard library sorting.
How to solve Find the Length of the Longest Common Prefix in O(n)?
A near linear solution can be achieved using a Trie. Insert every number from the first array digit by digit, then traverse the Trie with numbers from the second array while counting matching prefix depth. Each digit is processed once, giving roughly O(total_digits) time.
What is the best approach for Find the Length of the Longest Common Prefix?
The optimized approach converts numbers to strings, sorts them lexicographically, and compares adjacent values that originate from different arrays. Sorting groups numbers with similar prefixes together, reducing unnecessary comparisons. This results in roughly O((n+m) log(n+m) * L) time instead of checking every pair.
Is Find the Length of the Longest Common Prefix asked at Google/Amazon/Meta?
Prefix-based comparison problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving Tries, string prefixes, and lexicographic ordering are common because they test knowledge of string processing and data structures.
What data structure is used in Find the Length of the Longest Common Prefix?
Common solutions use string manipulation with arrays and sorting. More advanced implementations use a Trie (prefix tree) to efficiently store and query prefixes. Hash tables can also be used to store intermediate prefixes for quick lookup.
What is the time complexity of Find the Length of the Longest Common Prefix?
The brute force solution runs in O(n * m * L), where n and m are the array sizes and L is the number of digits. The optimized sorting approach improves performance to O((n+m) log(n+m) * L) by limiting comparisons to neighboring strings after sorting.