Find the length of the longest common prefix

Array Hash Table String Trie

57.0% acceptance

Feb 25, 2026

830

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. A common prefix of two integers a and b is an integer c, such that c is a prefix of both a and b. 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_common_prefix(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
    use std::collections::HashSet;
    let mut prefixes: HashSet<i32> = HashSet::new();
    for &x in &arr1 {
      let mut v = x;
      while v > 0 { prefixes.insert(v); v /= 10; }
    }
    let mut ans = 0;
    for &y in &arr2 {
      let mut v = y;
      while v > 0 {
        if prefixes.contains(&v) {
          let len = v.to_string().len() as i32;
          ans = ans.max(len);
        }
        v /= 10;
      }
    }
    ans
  }
}