Find the Length of the Longest Common Prefix - 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 common prefixes 565 and 5655 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.

Input & Output

Example 1 — Basic Case

$ Input: arr1 = [1,10,100], arr2 = [1000]

› Output: 3

💡 Note: The longest common prefix is between 100 and 1000: "100" has length 3

Example 2 — Multiple Matches

$ Input: arr1 = [1,2,3], arr2 = [4,4,4]

› Output: 0

💡 Note: No common prefixes exist between any pairs, so return 0

Example 3 — Single Digit Match

$ Input: arr1 = [1,10,100], arr2 = [1000,2000]

› Output: 3

💡 Note: The longest common prefix is between 100 and 1000: "100" has length 3

Constraints

1 ≤ arr1.length, arr2.length ≤ 5 × 10⁴
1 ≤ arr1[i], arr2[i] ≤ 10⁸

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 f Meta 8

The key insight is to convert numbers to strings and find common prefixes. The brute force approach compares every pair character by character, while the hash set approach stores all prefixes from arr1 for efficient lookup. Best approach is hash set with Time: O(n×k + m×k), Space: O(n×k) where k is average digits per number.

Common Approaches

✓ Brute Force String Comparison

⏱️ Time: O(n×m×k) Space: O(1)

Convert all numbers in both arrays to strings, then for each number in arr1, compare it with every number in arr2 to find the longest common prefix length.

Hash Set of All Prefixes

⏱️ Time: O(n×k + m×k) Space: O(n×k)

Generate all possible prefixes of numbers in arr1 and store them in a hash set. Then for each number in arr2, generate its prefixes and check if they exist in the set, keeping track of the maximum length.

Brute Force String Comparison — Algorithm Steps

Convert all numbers to strings
For each pair (x, y) from arr1 and arr2
Compare characters from left to right until mismatch
Track maximum prefix length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Convert to Strings

Transform numbers to strings for digit comparison

Compare Pairs

Check each arr1[i] vs arr2[j] character by character

Track Maximum

Keep the longest common prefix length found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr1, int arr1Size, int* arr2, int arr2Size) {
    int maxLength = 0;
    
    for (int i = 0; i < arr1Size; i++) {
        char str1[20];
        sprintf(str1, "%d", arr1[i]);
        
        for (int j = 0; j < arr2Size; j++) {
            char str2[20];
            sprintf(str2, "%d", arr2[j]);
            
            // Find common prefix length
            int commonLen = 0;
            int len1 = strlen(str1);
            int len2 = strlen(str2);
            int minLen = len1 < len2 ? len1 : len2;
            
            for (int k = 0; k < minLen; k++) {
                if (str1[k] == str2[k]) {
                    commonLen++;
                } else {
                    break;
                }
            }
            
            if (commonLen > maxLength) {
                maxLength = commonLen;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[1000];
    
    // Read first array
    fgets(line, sizeof(line), stdin);
    int arr1[1000], arr1Size = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        arr1[arr1Size++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    // Read second array
    fgets(line, sizeof(line), stdin);
    int arr2[1000], arr2Size = 0;
    token = strtok(line, "[],\n ");
    while (token != NULL) {
        arr2[arr2Size++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    printf("%d\n", solution(arr1, arr1Size, arr2, arr2Size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m×k)

Nested loops through arr1 (n) and arr2 (m), with string comparison up to k digits

✓ Linear Growth

Space Complexity

O(1)

Only storing temporary strings and variables, no extra data structures

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

320 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Find the Length of the Longest Common Prefix - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force String Comparison — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler