Store all prefixes of numbers from arr1 in a HashSet.
Example for 12345:
12345
1234
123
12
1
We get these prefixes by repeatedly dividing by 10.
Then for every number in arr2, keep removing digits from the end and check if that prefix exists in the set.
Example:
1239 → 123 → found
So common prefix length = 3.
break is used because further prefixes (12, 1) will only be smaller.
import java.util.HashSet;
class Solution {
public int longestCommonPrefix(int[] arr1, int[] arr2) {
HashSet<Integer> prefixes = new HashSet<>();
// Step 1: Insert all possible prefixes of numbers in arr1 into the HashSet
for (int val : arr1) {
while (val > 0) {
prefixes.add(val);
val /= 10; // Remove the last digit to get the next prefix
}
}
int maxLength = 0;
// Step 2: Check all possible prefixes of numbers in arr2 against the HashSet
for (int val : arr2) {
while (val > 0) {
if (prefixes.contains(val)) {
// Step 3: If found, calculate its length and update maxLength
int currentLength = String.valueOf(val).length();
maxLength = Math.max(maxLength, currentLength);
// Optimization: Since we are dividing by 10, subsequent prefixes
// of this specific 'val' will be shorter. We can break early.
break;
}
val /= 10;
}
}
return maxLength;
}
}