Find the Length of the Longest Common Prefix

Medium Tries Basics Original on LeetCode

Find the Length of the Longest Common Prefix is a medium tries problem solved with the basics pattern. The best approach, optimal (digit trie), runs in O((n + m) · d) time and O(n · d) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (compare every pair) up.

Problem

You get two arrays of positive integers, arr1 and arr2. A prefix of a number is formed by one or more of its leading digits: 305 is a prefix of 3051, but 51 is not.

For every pair (x, y) with x from arr1 and y from arr2, look at the longest prefix the two numbers share. Return the number of digits of the longest such shared prefix over all pairs, or 0 if no pair shares even a first digit.

Examples

Example 1

Input
arr1 = [3051, 77], arr2 = [305, 7712]
Output
3
Why
3051 and 305 share the prefix 305 (3 digits); 77 and 7712 share only 77 (2 digits).

Example 2

Input
arr1 = [9, 81], arr2 = [18, 27]
Output
0
Why
No number in arr1 starts with the same digit as any number in arr2.

Example 3

Input
arr1 = [5000, 5], arr2 = [5000]
Output
4
Why
5000 appears in both arrays, so the whole number (4 digits) is a common prefix.

Constraints

  • 1 <= arr1.length, arr2.length <= 5 * 10^4
  • 1 <= arr1[i], arr2[i] <= 10^8

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (compare every pair)O(n · m · d)O((n + m) · d)
Hash set of prefixesO((n + m) · d)O(n · d)
Optimal (digit trie)O((n + m) · d)O(n · d)

1Brute force (compare every pair)

TimeO(n · m · d)n · m pairs, each compared in up to d <= 9 digit steps.
SpaceO((n + m) · d)The digit strings of all numbers.

Turn each number into its digit string and, for every pair (x from arr1, y from arr2), count matching leading digits. Keep the maximum.

  1. Convert both arrays to strings.
  2. For every pair, walk both strings while their digits match.
  3. Track the largest matched length.
class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        String[] a = new String[arr1.length];
        String[] b = new String[arr2.length];
        for (int i = 0; i < arr1.length; i++) a[i] = String.valueOf(arr1[i]);
        for (int j = 0; j < arr2.length; j++) b[j] = String.valueOf(arr2[j]);
        int best = 0;
        for (String x : a) {
            for (String y : b) {
                int k = 0;
                while (k < x.length() && k < y.length() && x.charAt(k) == y.charAt(k)) k++;
                best = Math.max(best, k);
            }
        }
        return best;
    }
}

2Hash set of prefixes

TimeO((n + m) · d)Each number produces at most d <= 9 prefixes and each set operation is O(1) on average.
SpaceO(n · d)The set stores up to 9 prefixes per number of arr1.

Every number has at most 9 prefixes (drop the last digit until nothing is left). Put all prefixes of arr1 into a hash set. For each y in arr2, keep dropping its last digit until the value is in the set; the digit count of that value is a candidate answer.

  1. For each x in arr1: while x > 0, add x to the set and set x = x / 10.
  2. For each y in arr2: while y > 0 and y is not in the set, y = y / 10.
  3. If y > 0, update the answer with the number of digits of y.
class Solution {
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Set<Integer> prefixes = new HashSet<>();
        for (int x : arr1) {
            while (x > 0) {
                prefixes.add(x);
                x /= 10;
            }
        }
        int best = 0;
        for (int y : arr2) {
            while (y > 0 && !prefixes.contains(y)) y /= 10;
            if (y > 0) best = Math.max(best, String.valueOf(y).length());
        }
        return best;
    }
}

3Optimal (digit trie)

TimeO((n + m) · d)Each insertion and each walk visits at most d <= 9 nodes.
SpaceO(n · d)At most d new nodes per inserted number, each with 10 child slots.

Insert the digits of every number of arr1 into a trie with 10 children per node. For each number of arr2, walk the trie digit by digit from the most significant one; the depth where the walk stops is the longest prefix it shares with some number of arr1.

  1. Insert the digit string of each x in arr1 into the trie.
  2. For each y in arr2, follow its digits from the root while the child exists, counting the steps.
  3. The answer is the largest count.
class Solution {
    private static class Node {
        Node[] next = new Node[10];
    }

    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        Node root = new Node();
        for (int x : arr1) {
            Node cur = root;
            for (char c : String.valueOf(x).toCharArray()) {
                int d = c - '0';
                if (cur.next[d] == null) cur.next[d] = new Node();
                cur = cur.next[d];
            }
        }
        int best = 0;
        for (int y : arr2) {
            Node cur = root;
            int depth = 0;
            for (char c : String.valueOf(y).toCharArray()) {
                int d = c - '0';
                if (cur.next[d] == null) break;
                cur = cur.next[d];
                depth++;
            }
            best = Math.max(best, depth);
        }
        return best;
    }
}

Edge cases to test

  • No common first digit anywhere (answer 0)
  • The same number in both arrays (answer is its digit count)
  • One number is a prefix of the other, like 12 and 12345
  • Trailing zeros: 100 and 1000 share prefix 100

Hints

Hint 1

A prefix of a positive integer is obtained by repeatedly dropping its last digit (integer division by 10).

Hint 2

Store every prefix of every number in arr1 once; then for each number in arr2, find its longest prefix that you stored.

Hint 3

A trie over decimal digits answers "how far down can this number walk" directly.

FAQ

What is the best time complexity for Find the Length of the Longest Common Prefix?

Optimal (digit trie) runs in O((n + m) · d) time and O(n · d) extra space. Each insertion and each walk visits at most d <= 9 nodes.

Which pattern does Find the Length of the Longest Common Prefix use?

It is a tries problem that uses the basics pattern. Other problems with the same pattern: Implement Trie (Prefix Tree), Implement Trie ll, Design In-Memory File System.

Is there a brute force solution for Find the Length of the Longest Common Prefix?

Yes. Brute force (compare every pair) takes O(n · m · d) time and O((n + m) · d) space. Turn each number into its digit string and, for every pair (x from arr1, y from arr2), count matching leading digits.

Which edge cases should I test for Find the Length of the Longest Common Prefix?

No common first digit anywhere (answer 0); The same number in both arrays (answer is its digit count); One number is a prefix of the other, like 12 and 12345; Trailing zeros: 100 and 1000 share prefix 100.