3043. 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 a common prefix 565 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 01:

#include <iostream>
#include <memory>
#include <vector>
#include <string>
using namespace std;

struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  TrieNode() : children(10) {}  // Initializes children for digits 0-9
};

class Trie {
 public:
  // Insert a number string into the Trie
  void insert(const string& numberString) {
    shared_ptr<TrieNode> currentNode = root;
    for (const char digit : numberString) {
      const int index = digit - '0';  // Convert character to corresponding index
      if (currentNode->children[index] == nullptr)
        currentNode->children[index] = make_shared<TrieNode>();
      currentNode = currentNode->children[index];
    }
  }

  // Search for the longest common prefix of a number string
  int search(const string& numberString) {
    int commonPrefixLength = 0;
    shared_ptr<TrieNode> currentNode = root;
    for (const char digit : numberString) {
      const int index = digit - '0';
      if (currentNode->children[index] == nullptr)
        break;
      currentNode = currentNode->children[index];
      ++commonPrefixLength;
    }
    return commonPrefixLength;
  }

 private:
  shared_ptr<TrieNode> root = make_shared<TrieNode>();  // Root of the Trie
};

class Solution {
 public:
  // Function to find the longest common prefix between two arrays of integers
  int longestCommonPrefix(vector<int>& array1, vector<int>& array2) {
    int maxPrefixLength = 0;
    Trie trie;

    // Insert all numbers from array1 into the Trie
    for (const int number : array1)
      trie.insert(to_string(number));

    // Search for the longest common prefix with numbers in array2
    for (const int number : array2)
      maxPrefixLength = max(maxPrefixLength, trie.search(to_string(number)));

    return maxPrefixLength;
  }
};

class TrieNode:
    def __init__(self):
        # Initializes children for digits 0-9
        self.children = [None] * 10

class Trie:
    def __init__(self):
        # Root of the Trie
        self.root = TrieNode()

    # Insert a number string into the Trie
    def insert(self, numberString):
        currentNode = self.root
        for digit in numberString:
            index = ord(digit) - ord('0')  # Convert character to corresponding index
            if currentNode.children[index] is None:
                currentNode.children[index] = TrieNode()
            currentNode = currentNode.children[index]

    # Search for the longest common prefix of a number string
    def search(self, numberString):
        commonPrefixLength = 0
        currentNode = self.root
        for digit in numberString:
            index = ord(digit) - ord('0')
            if currentNode.children[index] is None:
                break
            currentNode = currentNode.children[index]
            commonPrefixLength += 1
        return commonPrefixLength

class Solution:
    # Function to find the longest common prefix between two arrays of integers
    def longestCommonPrefix(self, array1: List[int], array2: List[int]) -> int:
        maxPrefixLength = 0
        trie = Trie()

        # Insert all numbers from array1 into the Trie
        for number in array1:
            trie.insert(str(number))

        # Search for the longest common prefix with numbers in array2
        for number in array2:
            maxPrefixLength = max(maxPrefixLength, trie.search(str(number)))

        return maxPrefixLength

Time Complexity

• Inserting into the Trie:

  Each number from array1 is converted to a string and inserted into the Trie. For a number with \(d\) digits, insertion takes \(O(d)\), where \(d\) is the number of digits in the number. If the size of array1 is \(n_1\) and the maximum number of digits in a number is \(d_{\text{max}}\), then inserting all numbers takes \(O(n_1 \cdot d_{\text{max}})\).

• Searching the Trie:

  For each number in array2, we search for the longest common prefix. Similar to insertion, searching takes \(O(d)\) for a number with \(d\) digits. If the size of array2 is \(n_2\) and the maximum number of digits in a number is \(d_{\text{max}}\), then searching for all numbers takes \(O(n_2 \cdot d_{\text{max}})\).

• Overall Time Complexity:

  The overall time complexity is \(O((n_1 + n_2) \cdot d_{\text{max}})\), where:

  • \(n_1\) is the number of elements in array1
  • \(n_2\) is the number of elements in array2
  • \(d_{\text{max}}\) is the maximum number of digits in the numbers from both arrays.

Space Complexity

• Trie Node Storage:

  The Trie stores digits (0-9), so each node has 10 children pointers. For each number, we store up to \(d_{\text{max}}\) nodes. In the worst case, where all numbers from array1 are unique, we will have \(O(n_1 \cdot d_{\text{max}})\) nodes in the Trie.

• Auxiliary Space:

  We also use space for storing the Trie structure, along with a string conversion for each number (which takes \(O(d_{\text{max}})\) space for each number during insertion and search).

• Overall Space Complexity:

  The space complexity is \(O(n_1 \cdot d_{\text{max}})\), primarily due to storing the Trie nodes, where \(n_1\) is the number of elements in array1 and \(d_{\text{max}}\) is the maximum number of digits in the numbers.