Find the Length of the Longest Common Prefix

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: 1

💡 Note: Multiple numbers share prefix "1" but that's the longest common prefix with length 1

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two arrays of positive integers

Compare Prefixes

Find common prefixes between pairs from both arrays

Return Maximum

Length of the longest common prefix found

Key Takeaway

🎯 Key Insight: Convert numbers to strings and systematically compare prefixes to find the maximum common length

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

Approach	Time	Space	Notes
✓ Hash Set of All Prefixes	O(n×k + m×k)	O(n×k)	Store all possible prefixes of arr1 in a hash set, then check arr2 prefixes
Brute Force String Comparison	O(n×m×k)	O(1)	Convert numbers to strings and compare each pair character by character

Hash Set of All Prefixes — Algorithm Steps

Convert all numbers in arr1 to strings
Generate all prefixes of arr1 numbers and store in hash set
For each number in arr2, generate prefixes and check existence
Track the maximum prefix length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Prefixes

Create all possible prefixes from arr1 numbers

Store in Hash Set

Add prefixes to hash set for O(1) lookup

Check arr2

Generate arr2 prefixes and check if they exist in set

Code -

solution.c — C

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

#define MAX_PREFIXES 10000

char prefixes[MAX_PREFIXES][20];
int prefixCount = 0;

int findPrefix(char* prefix) {
    for (int i = 0; i < prefixCount; i++) {
        if (strcmp(prefixes[i], prefix) == 0) {
            return 1;
        }
    }
    return 0;
}

void addPrefix(char* prefix) {
    if (prefixCount < MAX_PREFIXES && !findPrefix(prefix)) {
        strcpy(prefixes[prefixCount++], prefix);
    }
}

int solution(int* arr1, int arr1Size, int* arr2, int arr2Size) {
    prefixCount = 0;
    
    // Store all prefixes from arr1
    for (int i = 0; i < arr1Size; i++) {
        char s[20];
        sprintf(s, "%d", arr1[i]);
        int len = strlen(s);
        
        for (int j = 1; j <= len; j++) {
            char prefix[20];
            strncpy(prefix, s, j);
            prefix[j] = '\0';
            addPrefix(prefix);
        }
    }
    
    int maxLength = 0;
    // Check all prefixes from arr2
    for (int i = 0; i < arr2Size; i++) {
        char s[20];
        sprintf(s, "%d", arr2[i]);
        int len = strlen(s);
        
        for (int j = 1; j <= len; j++) {
            char prefix[20];
            strncpy(prefix, s, j);
            prefix[j] = '\0';
            
            if (findPrefix(prefix)) {
                int prefixLen = strlen(prefix);
                if (prefixLen > maxLength) {
                    maxLength = prefixLen;
                }
            }
        }
    }
    
    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×k + m×k)

Generate k prefixes for each of n numbers in arr1, then k prefixes for each of m numbers in arr2

✓ Linear Growth

Space Complexity

O(n×k)

Hash set stores all prefixes from arr1, up to k prefixes per number

⚡ Linearithmic 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set of All Prefixes — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler