Leetcode Daily Question 24/09/2024 - 3043. Find the Length of the Longest Common Prefix

Problem Description:

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.

from typing import List
class Solution:
  def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
    max_length = 0 
    seen = set()
    
    for num in arr1:
      while num > 0 and num not in seen:
        seen.add(num)
       	num //= 10
        
    for num in arr2:
      while num > 0 and num not in seen:
        num //= 10
      if num > 0 and len(str(num)) > max_length:
        max_length = len(str(num))
        
    return max_length

Explanation:

Instead of brute forcing, we can use a hashset to store possible prefixes in arr1 and compare those prefixes to prefixes in arr2. This removes most of the unnecessary operations.

We can further reduce the use of extra memory by considering prefixes directly as integers. We remove the most significant digit one at a time to generate all possible prefixes.

Finally, instead of having to compare max_length with every possible case, we only update max_length when the new valid prefix found has longer length.

Let's first define and fill the hashset.

seen = set()

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

Then, we can fill in the rest of the logic

max_length = 0

for num in arr2:
  while num > 0 and num not in seen:
    num //= 10
  if num > 0 and len(str(num)) > max_length:
    max_length = len(str(num))
    
return max_length

The time complexity is O(n * d1 + m * d2), where n is length of arr1, m is length of arr2, d1 max length of num in arr1, d2 max length of num in arr2.

The space complexity is O(n * d1) since we only store prefixes in arr1.

The full solution can be found near the top of the page.