# Find the Length of the Longest Common Prefix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-length-of-the-longest-common-prefix)
Canonical: https://scaleengineer.com/dsa/problems/find-the-length-of-the-longest-common-prefix
**Data structures:** Array, Hash Table, String, Trie
**Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Visa](https://scaleengineer.com/companies/visa), [Capital One](https://scaleengineer.com/companies/capital-one), [Databricks](https://scaleengineer.com/companies/databricks), [Coinbase](https://scaleengineer.com/companies/coinbase), [The Trade Desk](https://scaleengineer.com/companies/the-trade-desk), [ZipRecruiter](https://scaleengineer.com/companies/ziprecruiter)
---
## 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 * 104`
* `1 <= arr1[i], arr2[i] <= 108`

# Approaches
## Brute Force Iteration
This approach directly implements the problem statement by checking every possible pair of numbers, one from `arr1` and one from `arr2`.
**Time:** O(N * M * D), where `N` is the length of `arr1`, `M` is the length of `arr2`, and `D` is the maximum number of digits in a number. This is because we have nested loops for `N*M` pairs, and for each pair, we compare strings of length up to `D`. This is too slow for the given constraints. · **Space:** O(D) for storing the string representations of two numbers at a time during comparison.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
We initialize a variable `maxLength` to 0 to store the length of the longest common prefix found so far.

We use nested loops to iterate through every number `x` in `arr1` and every number `y` in `arr2`.

For each pair `(x, y)`, we calculate the length of their common prefix. A helper function can be used for this. The helper function works by converting both numbers to strings. Then, it compares them character by character to find the length of the common prefix string.

After calculating the length for a pair, we update `maxLength` if the current length is greater.

Finally, after checking all pairs, `maxLength` holds the result.

```java
class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        int maxLength = 0;
        for (int num1 : arr1) {
            for (int num2 : arr2) {
                String s1 = String.valueOf(num1);
                String s2 = String.valueOf(num2);
                int currentLength = 0;
                int len = Math.min(s1.length(), s2.length());
                for (int i = 0; i < len; i++) {
                    if (s1.charAt(i) == s2.charAt(i)) {
                        currentLength++;
                    } else {
                        break;
                    }
                }
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- For each `num1` in `arr1`:
  - For each `num2` in `arr2`:
    - Convert `num1` and `num2` to strings `s1` and `s2`.
    - Find the length of the common prefix of `s1` and `s2`. Let this be `currentLength`.
    - Update `maxLength = max(maxLength, currentLength)`.
- Return `maxLength`.

## Optimized Search with a Hash Set
This approach avoids the inefficient nested loop by pre-processing one of the arrays. We generate all possible prefixes from one array and store them in a hash set. Then, for each number in the other array, we can efficiently check for its prefixes in the hash set.
**Time:** O((N + M) * D), where `N` and `M` are the lengths of the arrays and `D` is the max number of digits. Populating the set takes `O(M * D)` and searching takes `O(N * D)`. This is efficient enough. · **Space:** O(M * D) to store all prefixes from `arr2` in the hash set. In the worst case, all prefixes are unique.
**Pros:** Significantly faster than the brute-force approach.; Relatively easy to implement using a standard hash set.
**Cons:** Uses extra space to store prefixes, which can be large if `arr2` is large.
### Explanation
The core idea is to reduce the search time for a common prefix. Instead of comparing a number from `arr1` with every number in `arr2`, we can check if any prefix of the `arr1` number exists as a prefix in the `arr2` set.

1.  First, we create a `HashSet` of integers to store all prefixes of numbers from one of the arrays, say `arr2`.
2.  We iterate through each number `y` in `arr2`. For each `y`, we generate all its prefixes by repeatedly dividing it by 10 until it becomes 0. For example, if `y` is 123, we add 123, 12, and 1 to the set.
3.  After populating the set, we iterate through each number `x` in `arr1`. For each `x`, we check its prefixes against the set, starting from the longest prefix (the number `x` itself) down to the shortest.
4.  The first prefix we find in the set is guaranteed to be the longest common prefix for that particular `x`. We calculate its length and update our global `maxLength`. We can then break and move to the next number in `arr1`.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Set<Integer> prefixSet = new HashSet<>();
        for (int num : arr2) {
            int current = num;
            while (current > 0) {
                prefixSet.add(current);
                current /= 10;
            }
        }

        int maxLength = 0;
        for (int num : arr1) {
            int current = num;
            while (current > 0) {
                if (prefixSet.contains(current)) {
                    maxLength = Math.max(maxLength, String.valueOf(current).length());
                    break; 
                }
                current /= 10;
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Create a `HashSet<Integer>` called `prefixSet`.
- For each `num` in `arr2`:
  - Generate all its prefixes by repeatedly dividing by 10 and add them to `prefixSet`.
- Initialize `maxLength = 0`.
- For each `num` in `arr1`:
  - Check its prefixes from longest to shortest (by dividing by 10).
  - If a prefix is found in `prefixSet`:
    - Calculate its length.
    - Update `maxLength` with the new maximum length.
    - Break the inner loop (as we've found the longest for this `num`).
- Return `maxLength`.

## Trie (Prefix Tree) Based Solution
This is a highly optimized approach using a Trie, a tree-like data structure perfect for prefix-related problems. We insert all numbers from one array into the Trie and then search for the longest matching prefixes for numbers from the second array.
**Time:** O((N + M) * D), where `N` and `M` are the lengths of the arrays and `D` is the max number of digits. Building the Trie takes `O(M * D)`, and searching takes `O(N * D)`. · **Space:** O(M * D) in the worst case for the Trie nodes. It can be more space-efficient than a hash set if numbers in `arr2` share many common prefixes.
**Pros:** Highly efficient and a canonical solution for prefix-based problems.; Can be more space-efficient than a hash set.; No risk of hash collisions and potentially better performance due to memory locality.
**Cons:** More complex to implement from scratch compared to using a built-in hash set.
### Explanation
A Trie is a specialized tree used to store a set of strings, where paths from the root to a node represent prefixes. For this problem, we treat the numbers as strings of digits.

1.  First, we build a Trie by inserting all numbers from `arr2`. Each node in our Trie will have up to 10 children, one for each digit (0-9).
2.  To insert a number, we convert it to a string. Then, starting from the root of the Trie, we traverse down the tree, creating new nodes as needed for each digit.
3.  After building the Trie, we iterate through each number `x` in `arr1`. For each `x`, we convert it to a string and traverse the Trie from the root, following the path corresponding to its digits.
4.  We count the length of the path we successfully traverse. The traversal stops when we can't go further (i.e., a child node for a digit doesn't exist). This length is the longest prefix of `x` that is also a prefix of some number in `arr2`.
5.  We update a global `maxLength` with the maximum length found across all numbers in `arr1`.

```java
class TrieNode {
    TrieNode[] children = new TrieNode[10];
}

class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        TrieNode root = new TrieNode();
        
        for (int num : arr2) {
            String s = String.valueOf(num);
            TrieNode curr = root;
            for (char c : s.toCharArray()) {
                int digit = c - '0';
                if (curr.children[digit] == null) {
                    curr.children[digit] = new TrieNode();
                }
                curr = curr.children[digit];
            }
        }
        
        int maxLength = 0;
        for (int num : arr1) {
            String s = String.valueOf(num);
            TrieNode curr = root;
            int currentLength = 0;
            for (char c : s.toCharArray()) {
                int digit = c - '0';
                if (curr.children[digit] == null) {
                    break;
                }
                curr = curr.children[digit];
                currentLength++;
            }
            maxLength = Math.max(maxLength, currentLength);
        }
        
        return maxLength;
    }
}
```
### Algorithm
- Define a `TrieNode` class with an array of 10 children.
- Create a `root` `TrieNode`.
- For each `num` in `arr2`:
  - Convert `num` to a string `s`.
  - Insert `s` into the Trie by traversing from the `root` and creating nodes as needed.
- Initialize `maxLength = 0`.
- For each `num` in `arr1`:
  - Convert `num` to a string `s`.
  - Traverse the Trie from the `root` using the digits of `s`.
  - Count the number of steps (`currentLength`) until a path does not exist.
  - Update `maxLength = max(maxLength, currentLength)`.
- Return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestCommonPrefix(int[] arr1, int[] arr2) {
    Set<Integer> s = new HashSet<>();
    for (int x : arr1) {
      for (; x > 0; x /= 10) {
        s.add(x);
      }
    }
    int ans = 0;
    for (int x : arr2) {
      for (; x > 0; x /= 10) {
        if (s.contains(x)) {
          ans = Math.max(ans, String.valueOf(x).length());
          break;
        }
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} arr1 * @param {number[]} arr2 * @return {number} */ var longestCommonPrefix = function ( arr1 , arr2 ) { const s = new Set (); for ( let x of arr1 ) { for (; x ; x = Math . floor ( x / 10 )) { s . add ( x ); } } let ans = 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 ; };
```

### Python

```python
class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int: s = set() for x in arr1: while x: s . add(x) x //= 10 ans = 0 for x in arr2: while x: if x in s: ans = max(ans, len(str(x))) break x //= 10 return ans

```

### CPP

```cpp
class Solution {
public:
  int longestCommonPrefix(vector<int> &arr1, vector<int> &arr2) {
    unordered_set<int> s;
    for (int x : arr1) {
      for (; x; x /= 10) {
        s.insert(x);
      }
    }
    int ans = 0;
    for (int x : arr2) {
      for (; x; x /= 10) {
        if (s.count(x)) {
          ans = max(ans, (int)log10(x) + 1);
          break;
        }
      }
    }
    return ans;
  }
};

```