LeetCode 3043 - Find the Length of the Longest Common Prefix | Java Solution

LeetCode 3043

Find the Length of the Longest Common Prefix

Java Solution + Detailed Explanation

Problem Statement

Given two arrays arr1 and arr2, return the length of the longest common prefix between any two integers.

Example:

arr1 = [1,10,100]
arr2 = [1000]

Output = 3
        

Explanation:

• 1 and 1000 → common prefix = "1" → length = 1
• 10 and 1000 → common prefix = "10" → length = 2
• 100 and 1000 → common prefix = "100" → length = 3

Understanding the Problem

We need to compare numbers digit by digit from the beginning.

12345
12399

Common Prefix = 123
Length = 3
    

Common Mistake

Many beginners compare complete numbers:

if(arr1[i] == arr2[j])
    

But the problem is asking for common starting digits, not complete equality.

Brute Force Approach

Steps

• Convert numbers into strings
• Compare every pair
• Match characters from left to right
• Stop when mismatch occurs

Java Solution

class Solution {

    public int longestCommonPrefix(int[] arr1, int[] arr2) {

        int lcp = 0;

        for (int i = 0; i < arr1.length; i++) {

            String s1 = String.valueOf(arr1[i]);

            for (int j = 0; j < arr2.length; j++) {

                String s2 = String.valueOf(arr2[j]);

                int count = 0;

                int minLen = Math.min(s1.length(), s2.length());

                for (int k = 0; k < minLen; k++) {

                    if (s1.charAt(k) == s2.charAt(k)) {
                        count++;
                    } else {
                        break;
                    }
                }

                lcp = Math.max(lcp, count);
            }
        }

        return lcp;
    }
}
    

Time Complexity

O(N * M * D)
        

Where:

• N = size of arr1
• M = size of arr2
• D = number of digits

Optimized HashSet Approach

Instead of comparing every pair, we can store all prefixes of arr1 numbers.

Example

1234

Prefixes:
1
12
123
1234
    

Optimized Java Solution

class Solution {

    public int longestCommonPrefix(int[] arr1, int[] arr2) {

        HashSet<Integer> set = new HashSet<>();

        for (int num : arr1) {

            while (num > 0) {
                set.add(num);
                num /= 10;
            }
        }

        int ans = 0;

        for (int num : arr2) {

            while (num > 0) {

                if (set.contains(num)) {

                    ans = Math.max(
                        ans,
                        String.valueOf(num).length()
                    );

                    break;
                }

                num /= 10;
            }
        }

        return ans;
    }
}
    

Optimized Complexity

Time Complexity: O((N + M) * D)

Space Complexity: O(N * D)
        

Why HashSet Works?

Every time we divide a number by 10:

12345
1234
123
12
1
    

These are exactly all possible prefixes.

Interview Tips

• Whenever you hear "prefix", think about Trie or HashSet
• String conversion is easy but slower
• Integer prefix removal is more optimized
• Always compare digit-by-digit for prefix problems

Conclusion

LeetCode 3043 is a great interview problem to learn:

• Prefix matching
• HashSet optimization
• String comparison
• Efficient problem-solving techniques

---

Practice More DSA Problems 🚀

Keep practicing coding interview questions regularly to improve your problem-solving skills and crack top tech companies.