We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Length of the Longest Common Prefix

Number: 3329

Difficulty: Medium

Paid? No

Companies: Meta, TikTok, Uber, Capital One, Google, Roblox, Databricks, Coinbase, The Trade Desk

Problem Description

You are given two arrays, arr1 and arr2, containing positive integers. A prefix of a positive integer is formed by one or more of its digits starting from the leftmost digit. A common prefix of two integers is a number that is a prefix of both. The task is to find the length of the longest common prefix among all pairs (x, y) such that x is from arr1 and y is from arr2. If no common prefix exists among any such pair, return 0.

Key Insights

  • Convert each integer into its string representation to easily extract and compare prefixes.
  • For any integer, you can derive all possible prefixes (e.g., "12345" gives "1", "12", "123", "1234", "12345").
  • Instead of comparing every pair (which would be inefficient), generate a set of all prefixes for arr1 and another set for arr2, then find the intersection of these sets.
  • The result is the maximum length among all common prefixes.

Space and Time Complexity

Time Complexity: O((n + m) * d), where n and m are the lengths of arr1 and arr2 respectively, and d is the maximum number of digits (at most 9).
Space Complexity: O((n + m) * d) for storing all prefixes in sets.

Solution

The approach involves converting the numbers in each array into strings and generating all possible prefixes for each number. We then store these prefixes in two sets (one for each array) and compute the intersection to obtain the common prefixes. The length of the longest prefix in this intersection is the answer. This method avoids checking every pair individually and leverages set operations for efficiency.

Code Solutions

# Python solution with line-by-line comments

def longest_common_prefix_length(arr1, arr2):
    # Helper function to generate all prefixes of a given number string
    def get_prefixes(num_str):
        prefixes = set()
        for i in range(1, len(num_str) + 1):
            prefixes.add(num_str[:i])
        return prefixes

    # Build a set of prefixes from arr1
    prefixes1 = set()
    for num in arr1:
        s = str(num)  # Convert the number to a string
        prefixes1.update(get_prefixes(s))  # Add all prefixes of the number

    # Build a set of prefixes from arr2
    prefixes2 = set()
    for num in arr2:
        s = str(num)  # Convert the number to a string
        prefixes2.update(get_prefixes(s))  # Add all prefixes of the number

    # Find common prefixes between arr1 and arr2
    common_prefixes = prefixes1.intersection(prefixes2)
    
    # Determine the longest common prefix length
    max_length = 0
    for prefix in common_prefixes:
        max_length = max(max_length, len(prefix))
    
    return max_length

# Example usage:
print(longest_common_prefix_length([1,10,100], [1000]))  # Expected output: 3
print(longest_common_prefix_length([1,2,3], [4,4,4]))      # Expected output: 0
← Back to All Questions