The Indian Engineer

Problem 3043 Find the Length of the Longest Common Prefix

Posted on 7 mins

Array Hash-Table String Trie

Table of Contents

Problem Statement

Link - Problem 3043

Question

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:

Solution 

class TrieNode {
    public:
    TrieNode* children[10];
    TrieNode(){
        for(auto& child:children)
            child = nullptr;
    }
};

class Trie{
    public:
    TrieNode* root;

    Trie(){
        root = new TrieNode();
    }

    void insert(int num){
        TrieNode* temp = root;
        string str = to_string(num);
        for(char ch:str){
            int index = ch-'0';
            if(!temp->children[index])
                temp->children[index] = new TrieNode();
            temp = temp->children[index];
        }
    }

    int findLongPrefix(int num){
        TrieNode* temp = root;
        string str = to_string(num);
        int len = 0;

        for(char ch:str){
            int index = ch -'0';
            if(temp->children[index]){
                len++;
                temp = temp->children[index];
            }
            else
                break;
        }
        return len;
    }
};

class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        Trie t;
        for(int num: arr1)
            t.insert(num);

        int res = 0;

        for(int num:arr2){
            res = max(res,t.findLongPrefix(num));
        }
        return res;
    }
};

Complexity Analysis 

| Algorithm | Time Complexity | Space Complexity |
| --------- | --------------- | ---------------- |
| Trie      | O(nm logm)      | O(nm)            |

Explanation

Intial Thoughts

To solve this problem, think of comparing strings, consider using a data structure like a trie to store and compare prefixes efficiently. The key idea is to find a common prefix between two sets of numbers, so focus on how to store and compare these numbers in a way that allows for efficient prefix matching. Consider breaking down the problem into smaller steps, such as inserting numbers from one array into the trie and then checking for prefixes from the other array. Key points to consider include how to efficiently insert numbers into the trie, how to find the longest common prefix, and how to handle cases where no common prefix exists.

Intuitive Analysis

Imagine you’re building a tree where each branch represents a digit in a number. For each number in the first array, you add its digits to the tree, creating new branches as needed. Then, for each number in the second array, you follow the branches in the tree as far as you can, counting how many digits match. The longest match you find is your answer. Think about how this process can be optimized, such as stopping as soon as you find a mismatch, and how to compare the lengths of the common prefixes found for each pair of numbers to determine the overall longest common prefix. Consider using the trie data structure to store the numbers from the first array and then checking for prefixes from the second array, focusing on the steps involved in inserting numbers into the trie and checking for the longest common prefix.

1. Intuition

2. Implementation

Complexity Analysis

Time Complexity:

Space Complexity:

Footnote

This question is rated as Medium difficulty.

Hints

Put all the possible prefixes of each element in arr1 into a HashSet.

For all the possible prefixes of each element in arr2, check if it exists in the HashSet.

Similar Questions:

Title URL Difficulty
Longest Common Prefix https://leetcode.com/problems/longest-common-prefix Easy
Longest Common Suffix Queries https://leetcode.com/problems/longest-common-suffix-queries Hard