Find the Length of the Longest Common Prefix

Leetcode Problem:

• Find the Length of the Longest Common Prefix

Summary

• Find the length of the longest common prefix among all pairs of integers (x, y) such that x belongs to arr1 and y belongs to arr2.

Approach

• Use a set to store the digits of the numbers in arr1 and then for each number in arr2, check if the digits are present in the set
• If they are, update the answer with the maximum count of digits found so far.

Complexity

• O(n*m*log(max(arr1[i], arr2[i]))) where n is the size of arr1 and m is the size of arr2

Explain

• The time complexity of this solution is O(n*m*log(max(arr1[i], arr2[i]))) because for each number in arr1, we are inserting its digits into the set, and for each number in arr2, we are checking if its digits are present in the set
• The space complexity is O(n*m) because we are storing all the digits in the set.

Solution Code:

class Solution {
public:
    set s;
    int getCount(int a){
        int cnt = 0;
        while(a){
            cnt++;
            a /= 10;
        }
        return cnt;
    }
    int longestCommonPrefix(vector& arr1, vector& arr2) {
        int ans = 0;
        for(int i = 0 ; i < arr1.size(); i++){
            while(arr1[i]){
                s.insert(arr1[i]);
                arr1[i] /= 10;
            }
        }
        for(int i = 0 ; i < arr2.size(); i++){
            while(arr2[i]){
                if (s.find(arr2[i]) != s.end()){
                    ans = max(ans, getCount(arr2[i]));
                    break;
                }
                arr2[i] /= 10;
            }
        }
        return ans;
    }
};