3043. Find the Length of the Longest Common Prefix LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3043. Find the Length of the Longest Common Prefix LeetCode Solution with the best time and space complexity. The solution to Find the Length of the Longest Common Prefix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find the Length of the Longest Common Prefix solution in C++
Find the Length of the Longest Common Prefix solution in Java
Find the Length of the Longest Common Prefix solution in Python
Additional Resources

3043. Find the Length of the Longest Common Prefix LeetCode Solution image

Problem Statement of Find the Length of the Longest Common Prefix

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

Complexity Analysis

Time Complexity: O(|\texttt{arr1}| + |\texttt{arr2}|)
Space Complexity: O(|\texttt{arr1}| + |\texttt{arr2}|)

3043. Find the Length of the Longest Common Prefix LeetCode Solution in C++

struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  TrieNode() : children(10) {}
};

class Trie {
 public:
  void insert(const string& word) {
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - '0';
      if (node->children[i] == nullptr)
        node->children[i] = make_shared<TrieNode>();
      node = node->children[i];
    }
  }

  int search(const string& word) {
    int prefixLength = 0;
    shared_ptr<TrieNode> node = root;
    for (const char c : word) {
      const int i = c - '0';
      if (node->children[i] == nullptr)
        break;
      node = node->children[i];
      ++prefixLength;
    }
    return prefixLength;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();
};

class Solution {
 public:
  int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
    int ans = 0;
    Trie trie;

    for (const int num : arr1)
      trie.insert(to_string(num));

    for (const int num : arr2)
      ans = max(ans, trie.search(to_string(num)));

    return ans;
  }
};
/* code provided by PROGIEZ */

3043. Find the Length of the Longest Common Prefix LeetCode Solution in Java

class TrieNode {
  public TrieNode[] children = new TrieNode[10];
}

class Trie {
  public void insert(final String word) {
    TrieNode node = root;
    for (final char c : word.toCharArray()) {
      final int i = c - '0';
      if (node.children[i] == null)
        node.children[i] = new TrieNode();
      node = node.children[i];
    }
  }

  public int search(final String word) {
    int prefixLength = 0;
    TrieNode node = root;
    for (final char c : word.toCharArray()) {
      final int i = c - '0';
      if (node.children[i] == null)
        break;
      node = node.children[i];
      ++prefixLength;
    }
    return prefixLength;
  }

  private TrieNode root = new TrieNode();
}

class Solution {
  public int longestCommonPrefix(int[] arr1, int[] arr2) {
    int ans = 0;
    Trie trie = new Trie();

    for (final int num : arr1)
      trie.insert(Integer.toString(num));

    for (final int num : arr2)
      ans = Math.max(ans, trie.search(Integer.toString(num)));

    return ans;
  }
}
// code provided by PROGIEZ

3043. Find the Length of the Longest Common Prefix LeetCode Solution in Python

class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = {}


class Trie:
  def __init__(self):
    self.root = TrieNode()

  def insert(self, word: str) -> None:
    node: TrieNode = self.root
    for c in word:
      node = node.children.setdefault(c, TrieNode())
    node.isWord = True

  def search(self, word: str) -> int:
    prefixLength = 0
    node = self.root
    for c in word:
      if c not in node.children:
        break
      node = node.children[c]
      prefixLength += 1
    return prefixLength


class Solution:
  def longestCommonPrefix(self, arr1: list[int], arr2: list[int]) -> int:
    trie = Trie()

    for num in arr1:
      trie.insert(str(num))

    return max(trie.search(str(num)) for num in arr2)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents