3043. Find the Length of the Longest Common Prefix

Description

Given two arrays of integers arr1 and arr2, the task is to find the longest common prefix between any number from arr1 and any number from arr2. The prefix of a number refers to any number formed from its leading digits.

For example, if arr1 = [1234] and arr2 = [12, 5678], the longest common prefix between any number from both arrays is 2 (i.e., "12").

Intuition

To solve this problem efficiently, the main idea is to precompute all possible prefixes of the numbers in the first array and store them in a data structure. Once we have the prefixes from arr1, we can iterate over the numbers in arr2 and check for the longest matching prefix by comparing prefixes from both arrays.

Approach

1. Store Prefixes of arr1: For each number in arr1, generate all possible prefixes (i.e., from the first digit to the full number). Store these prefixes in a set for quick lookup.
2. Compare with arr2: For each number in arr2, check its longest prefix that exists in the set of prefixes from arr1. Keep track of the maximum length of matching prefixes.
3. Return Result: After comparing all numbers in arr2, the maximum matching prefix length is returned as the result.

Complexity

Time Complexity

• Building the set: For each number in arr1, we generate all prefixes. For a number with d digits, there are d prefixes. Therefore, if there are n numbers in arr1, the time complexity to build the prefix set is approximately O(n * d).
• Checking arr2: For each number in arr2, we check its prefixes. Again, for each number with d digits, this takes O(d) time. Thus, if there are m numbers in arr2, the time complexity for this step is O(m * d).

Therefore, the overall time complexity is O(n * d + m * d) where n and m are the lengths of arr1 and arr2, and d is the number of digits in the longest number.

Space Complexity

• The space complexity is dominated by the space used to store the prefixes from arr1. If the maximum length of the numbers is d, then in the worst case, we store n * d characters in the set. Thus, the space complexity is O(n * d).

Code

C++

class Solution {
public:
    int longestCommonPrefix(vector& arr1, vector& arr2) {
        set prefixes;
        
        // Insert all prefixes of elements in arr1 into the set
        for (int num : arr1) {
            string strNum = to_string(num);
            for (int i = 1; i <= strNum.length(); i++) {
                prefixes.insert(strNum.substr(0, i));
            }
        }

        int maxPrefixLength = 0;

        // Find the longest matching prefix from arr2
        for (int num : arr2) {
            string strNum = to_string(num);
            for (int i = strNum.length(); i > 0; i--) {
                string prefix = strNum.substr(0, i);
                if (prefixes.find(prefix) != prefixes.end()) {
                    maxPrefixLength = max(maxPrefixLength, i);
                    break;
                }
            }
        }

        return maxPrefixLength;
    }
};

Python

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

        # Insert all prefixes of elements in arr1 into the set
        for num in arr1:
            str_num = str(num)
            for i in range(1, len(str_num) + 1):
                prefixes.add(str_num[:i])

        max_prefix_length = 0

        # Find the longest matching prefix from arr2
        for num in arr2:
            str_num = str(num)
            for i in range(len(str_num), 0, -1):
                prefix = str_num[:i]
                if prefix in prefixes:
                    max_prefix_length = max(max_prefix_length, i)
                    break

        return max_prefix_length

Java

class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Set prefixes = new HashSet<>();
        
        // Insert all prefixes of elements in arr1 into the set
        for (int num : arr1) {
            String strNum = Integer.toString(num);
            for (int i = 1; i <= strNum.length(); i++) {
                prefixes.add(strNum.substring(0, i));
            }
        }

        int maxPrefixLength = 0;

        // Find the longest matching prefix from arr2
        for (int num : arr2) {
            String strNum = Integer.toString(num);
            for (int i = strNum.length(); i > 0; i--) {
                String prefix = strNum.substring(0, i);
                if (prefixes.contains(prefix)) {
                    maxPrefixLength = Math.max(maxPrefixLength, i);
                    break;
                }
            }
        }

        return maxPrefixLength;
    }
}

JavaScript

var longestCommonPrefix = function (arr1, arr2) {

    let set = new Set();
    for (let num of arr1) {

        let i = 0;
        let strNum = num.toString();
        for(let i = 1; i <= strNum.length; i++){
            set.add(strNum.slice(0,i));
        }
    }
        let max = 0;
        for (let num of arr2) {

            let strNum = num.toString();
            for(let i = strNum.length; i > -1; i--){
                let prefix = strNum.slice(0,i);
                if(set.has(prefix)){
                    
                    max = Math.max(i, max);
                    break;
                }
            }
        }
        return max;
    };