3043. Find the Length of the Longest Common Prefix

Problem Description

In this problem, we are given two arrays of positive integers, arr1 and arr2. We are tasked with finding the length of the longest common prefix between any two integers, where one integer comes from arr1 and the other comes from arr2.

A "prefix" in this context means the digits at the start of an integer, up until any length of that integer. For instance, 12 is a prefix of 123. If a prefix is found in both integers from arr1 and arr2, it is considered a common prefix. Note that if the prefix doesn't exist in both integers, it's not common.

Our goal is to determine the size of the utmost common prefix discovered among all possible pairs made by taking one integer from each of the two arrays. If no common prefixes are found, then the answer we return should be 0.

Intuition

To solve this problem, we apply the concept of storing the prefixes in a hash table. The solution revolves around two main steps:

Firstly, we enumerate all possible prefixes from the integers in arr1 and store each one in a set (which acts as our hash table).

Secondly, for every integer in arr2, we start with the integer itself and keep dividing it by 10 (which effectively removes the least significant digit) to generate its prefixes. Each generated prefix is checked against our hash table to see if it's a common prefix.

The logic behind gradually reducing the integer starting from its original value down to its high-order digits is that we are interested in the longest common prefix – so we start with checking the entire number and then reduce it from the right.

While we are checking for prefixes, we remember the length of the longest common prefix we've encountered by using a variable. This variable is updated anytime we find a longer common prefix than the current record.

This approach allows us to efficiently find the longest common prefix among all pairs by leveraging the quick lookup capabilities of a hash table.

Learn more about Trie patterns.

Solution Approach

The solution can be broken down into two main phases, using the Python programming language:

1. Prefix Generation for arr1:

   • We initiate by creating an empty set s, which will be used to store the prefixes of the integers present in arr1.
   • For each number x in arr1, we start a loop where we keep adding x to our set s. Right after adding, we divide x by 10 using an integer division (x //= 10). This effectively removes the least significant digit of x, leaving us with a new prefix. We repeat this until x becomes 0, which means we've added all possible prefixes of x to the set.

2. Finding Longest Common Prefix with arr2:

   • We initialize an answer variable ans to 0. This will hold the length of the longest common prefix we find.
   • We iterate through each number x of arr2. Similar to the first phase, we keep dividing x by 10 to get its prefixes.
   • For each generated prefix of x, we check if this prefix exists in the set s. If it does, it means we have found a common prefix. We then compare the length of this prefix (by converting it to a string and getting the length) to our variable ans. If the length is greater, we update ans to the new length.
   • As soon as we find a matching prefix, we break out of the loop for the current number x because we're looking for the longest common prefix, and any further divisions will only produce shorter prefixes which are not of interest.

In summary, the solution utilizes a hash set for quick existence checks of prefixes, a loop to generate all possible prefixes of integers in arr1, and another loop to check prefixes of integers in arr2 against this set. We also use the max function to update the length of the longest common prefix as we iterate through the elements of arr2. This approach guarantees that we find the longest common prefix in an efficient manner.

Example Walkthrough

Let's illustrate the solution with a small example using the following arrays:

• arr1 = [12345, 678]
• arr2 = [123, 458]

Prefix Generation for arr1

• Initialize set s = {}.
• For 12345 in arr1:
  • Add 12345 to s, now s = {12345}.
  • Iterate by dividing by 10 and adding to s: 1234, 123, 12, 1, until x becomes 0. s becomes {12345, 1234, 123, 12, 1}.
• For 678 in arr1:
  • Add 678 to s, now s = {12345, 1234, 123, 12, 1, 678}.
  • Continue dividing by 10 and adding to s: 67, 6.
  • Final s = {12345, 1234, 123, 12, 1, 678, 67, 6}.

Finding Longest Common Prefix with arr2

• Initialize ans = 0.
• For 123 in arr2:
  • 123 is in set s. A common prefix of length 3 is found.
  • Update ans = 3 because it is greater than the current ans value.
  • No need to keep dividing 123 by 10 because we found the longest prefix with it.
• For 458 in arr2:
  • 458 is not in s.
  • Divide by 10, get 45. 45 not in s.
  • Divide by 10, get 4. 4 not in s.
  • All prefixes checked, move to next integer.

After iterating through both arrays, the longest common prefix we found was of length 3. Hence, our answer is 3.

1Given `arr1 = [12345, 678]` and `arr2 = [123, 458]`, let's walk through the solution step by step.
2
31. Prefix Generation for `arr1`:
4   - Create an empty set `s = {}`.
5   - Add all prefixes of `12345` to `s`. We add `12345`, `1234`, `123`, `12`, and `1`.
6   - Add all prefixes of `678` to `s`. We add `678`, `67`, and `6`.
7   - Now, `s = {12345, 1234, 123, 12, 1, 678, 67, 6}`.
8
92. Finding Longest Common Prefix with `arr2`:
10   - Initialize `ans = 0`.
11   - Look at `123` from `arr2`. We find `123` in `s`. Update `ans` to `3` since `123` has length `3`.
12   - Look at `458` from `arr2`. We do not find `458`, `45`, or `4` in `s`. We do not update `ans`.
13 
14The longest common prefix found is of length `3`, making our final answer `3`.

Solution Implementation

Time and Space Complexity

The time complexity of the algorithm is O(m * log M + n * log N), where m is the length of arr1, n is the length of arr2, M is the maximum value in arr1, and N is the maximum value in arr2. This is because for each element in arr1 and arr2, the algorithm potentially divides the element by 10 until it reaches 0, which occurs in O(log M) or O(log N) time for each element respectively.

The space complexity of the algorithm is O(m * log M) because the algorithm stores each prefix of the numbers from arr1 in a set. The number of prefixes for a number with a logarithmic number of digits is also logarithmic, so each number contributes O(log M) space, and there are m numbers in arr1.

Learn more about how to find time and space complexity quickly using problem constraints.