Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3
4

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.

Solution

Method 1 - Naive approach

We can run nested loops between arr1 and arr2 and calculate the common prefix length of digits between all numbers using commonPrefixLen(a, b).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        int maxLength = 0;
        for (int x : arr1) {
            for (int y : arr2) {
                maxLength = Math.max(maxLength, commonPrefixLen(x, y));
            }
        }
        return maxLength;
    }
    private int commonPrefixLen(int a, int b) {
        int maxLenA = getDigitLength(a);
        int maxLenB = getDigitLength(b);
        int maxLen = Math.min(maxLenA, maxLenB);

        int length = 0;
        while (length < maxLen
            && getDigit(a, maxLenA - 1 - length)
                == getDigit(b, maxLenB - 1 - length)) {
            length++;
        }

        return length;
    }    
    private int getDigitLength(int number) {
        int length = 0;
        while (number > 0) {
            number /= 10;
            length++;
        }
        return length;
    }

    private int getDigit(int number, int place) { // place starts from 0
        return (number / (int) Math.pow(10, place)) % 10;
    }

}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        max_length = 0
        for x in arr1:
            for y in arr2:
                max_length = max(
                    max_length, self.common_prefix_length(x, y)
                )
        return max_length
    def common_prefix_length(self, a: int, b: int) -> int:
        length = 0
        factor = 1
        while a // factor != 0 and b // factor != 0:
            if (a // factor) % 10 != (b // factor) % 10:
                break
            length += 1
            factor *= 10
        return length

Complexity

  • ⏰ Time complexity: O(m * n * min(log10(a), log10(b)), where m is the length of arr1, n is the length of arr2, and a and b are typical values in the arrays. This accounts for the nested loops and digit comparisons.
  • 🧺 Space complexity: O(1), as no additional space is used apart from a few variables.

Method 2 - String Conversion and naive prefix comparison

Here is the approach:

  1. Nested Loop for Integer Pairs:
    • For each pair (x, y), where x is from arr1 and y is from arr2, compute the length of the common prefix.
  2. Common Prefix Function:
    • Compare the digits of the two integers as strings to find the length of the common prefix.
  3. Update Maximum Length:
    • Track the maximum prefix length encountered during the nested loops.
  4. Return Result:
    • Return the longest common prefix length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        int maxLength = 0;

        for (int x : arr1) {
            for (int y : arr2) {
                maxLength = Math.max(maxLength, commonPrefixLen(x, y));
            }
        }

        return maxLength;
    }

    private  int commonPrefixLen(int a, int b) {
        String aStr = String.valueOf(a);
        String bStr = String.valueOf(b);
        int minLen = Math.min(aStr.length(), bStr.length());

        for (int i = 0; i < minLen; i++) {
            if (aStr.charAt(i) != bStr.charAt(i)) {
                return i;
            }
        }

        return minLen;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def get_digit_length(self, number):
        length = 0
        while number > 0:
            number //= 10
            length += 1
        return length

    def get_digit(self, number, place):  # place starts from 0
        return (number // (10**place)) % 10

    def common_prefix_len(self, a, b):
        max_len_a = self.get_digit_length(a)
        max_len_b = self.get_digit_length(b)
        max_len = min(max_len_a, max_len_b)

        length = 0
        while length < max_len and self.get_digit(
            a, max_len_a - 1 - length
        ) == self.get_digit(b, max_len_b - 1 - length):
            length += 1

        return length

    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        max_length = 0
        for x in arr1:
            for y in arr2:
                max_length = max(max_length, self.common_prefix_len(x, y))

        return max_length

Complexity

  • ⏰ Time complexity: O(m * n * min(l1, l2)), where m is the length of arr1, n is the length of arr2, and l1 and l2 are the lengths of integers (converted to strings).
  • 🧺 Space complexity: O(1)

Method 3 - Using Hashset of prefixes

Here is the approach:

  1. Building Prefix Set:
    • Iterate through arr1, and for each number, add all its prefixes to prefix_set until it has no more prefixes.
  2. Finding Longest Common Prefix:
    • For each number in arr2, reduce it to its prefixes and check if any prefix exists in prefix_set.
    • If a common prefix is found, calculate its length and update max_length if it’s the longest found so far.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Set<Integer> prefixSet = new HashSet<>();
        for (int num : arr1) {
	        while (num != 0 && !prefixSet.contains(num)) {
		        prefixSet.add(num);
		        num = num / 10;
	        }
        }

        int maxLength = 0;
        for (int num : arr2) {
            while (num != 0 && !prefixSet.contains(num)) {
		        num = num / 10;
	        }
			if (num != 0) {
				maxLength = Math.max(maxLength, Integer.toString(num).length());
			}
        }

        return maxLength;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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

        for num in arr1:
            while num != 0 and num not in prefix_set:
                prefix_set.add(num)
                num //= 10

        max_length = 0
        for num in arr2:
            original_num = num
            while num != 0 and num not in prefix_set:
                num //= 10
            if num != 0:
                max_length = max(
                    max_length, len(str(original_num)) - len(str(num))
                )

        return max_length

Complexity

  • ⏰ Time complexity: O(m log10(a) + n log10(b))), where m is the length of arr1, n is the length of arr2, and a and b are typical values in these arrays. This accounts for the nested loops and digit comparisons.
  • 🧺 Space complexity: O(m * l1), where l1 is the length of the longest integer in arr1 

Method 4 - Using Trie

Using a prefix tree (Trie) can indeed be an efficient way to solve this problem. A Trie is ideal for problems involving prefixes, as it allows for efficient insertion and search operations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66


public class Solution {
	class TrieNode {
	    Map<Integer, TrieNode> children = new HashMap<>();
	    boolean isEndOfNumber = false;
	}
	
	class Trie {
	    TrieNode root = new TrieNode();
	
	    void insert(int number) {
	        TrieNode currentNode = root;
	        List<Integer> digits = getDigits(number);
	        for (int digit : digits) {
	            currentNode.children.putIfAbsent(digit, new TrieNode());
	            currentNode = currentNode.children.get(digit);
	        }
	        currentNode.isEndOfNumber = true;
	    }
	
	    int searchCommonPrefixLength(int number) {
	        TrieNode currentNode = root;
	        List<Integer> digits = getDigits(number);
	        int length = 0;
	        for (int digit : digits) {
	            if (currentNode.children.containsKey(digit)) {
	                length++;
	                currentNode = currentNode.children.get(digit);
	            } else {
	                break;
	            }
	        }
	        return length;
	    }
	
	    private List<Integer> getDigits(int number) {
	        List<Integer> digits = new ArrayList<>();
	        while (number > 0) {
	            digits.add(0, number % 10);
	            number /= 10;
	        }
	        return digits;
	    }
	}
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Trie trie = new Trie();
        for (int num : arr1) {
            trie.insert(num);
        }

        int maxLength = 0;
        for (int num : arr2) {
            maxLength = Math.max(maxLength, trie.searchCommonPrefixLength(num));
        }

        return maxLength;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr1 = {12345, 6789, 123};
        int[] arr2 = {123, 67895, 567};
        System.out.println(
            solution.longestCommonPrefix(arr1, arr2)); // Output: 3
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_number = False


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

    def insert(self, number: int):
        current_node = self.root
        digits = list(map(int, str(number)))
        for digit in digits:
            if digit not in current_node.children:
                current_node.children[digit] = TrieNode()
            current_node = current_node.children[digit]
        current_node.is_end_of_number = True

    def search_common_prefix_length(self, number: int) -> int:
        current_node = self.root
        digits = list(map(int, str(number)))
        length = 0
        for digit in digits:
            if digit in current_node.children:
                length += 1
                current_node = current_node.children[digit]
            else:
                break
        return length

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        trie = Trie()
        for num in arr1:
            trie.insert(num)

        max_length = 0
        for num in arr2:
            max_length = max(max_length, trie.search_common_prefix_length(num))

        return max_length

Complexity

  • ⏰ Time complexity: O(m * l1 + n * l2), where m and n are the lengths of arr1 and arr2, and l1 and l2 are the number of digits in the longest numbers in arr1 and arr2.
  • 🧺 Space complexity: O(m * l1), where m is the length of arr1 and l1 is the length of the longest number in arr1.