Skip to main content
Talentd

Find the Length of the Longest Common Prefix - Solution & Explanation

MediumArrayHash TableStringTrie21 min readAsked at: Amazon, Microsoft, Meta +14
Practice this problem

Problem Statement

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 * 104
  • 1 <= 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.

This C solution utilizes a nested loop to iterate through each combination of numbers from arr1 and arr2. For each combination, it finds the common prefix length using a helper function that compares the string representations of the numbers. The maximum prefix length found is returned.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(n * m * k), Space complexity: O(1)

Try this approach in the editor →

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).

This C solution uses sorting to increase the efficiency of comparisons. Once the arrays are sorted, potential longer common prefixes only appear among consecutive elements, reducing unnecessary computations and leading to quicker results.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Average Time complexity: O(n log n + m log m + n + m), Space complexity: O(1)

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Prefix ComparisonO(n * m * L)O(1)Small input sizes or when explaining the base idea in interviews
Optimized String Comparison Using SortingO((n + m) log(n + m) * L)O(n + m)General case with larger arrays where reducing pair comparisons improves performance

Video Solution

Find the Length of the Longest Common Prefix | 2 Approaches | Leetcode 3043 | codestorywithMIK • codestorywithMIK • 20,727 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find the Length of the Longest Common Prefix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Common Prefix

Next

Longest Common Suffix Queries