Skip to content

Latest commit

 

History

History
109 lines (74 loc) · 4.18 KB

explanation.md

File metadata and controls

109 lines (74 loc) · 4.18 KB
Raw

Longest Common Prefix Between Two Arrays - Explanation

Problem Statement

Given two arrays of integers, find the length of the longest common prefix between any number from the first array (arr1) and any number from the second array (arr2). A "prefix" is defined as the initial characters of a number when represented as a string.

C++ Code Explanation

  1. Prefix Storage:

    • An unordered map (prefixMap) is used to store the prefixes of the numbers from the first array (arr1).

  2. Building the Prefix Map:

    • Convert each number from arr1 to a string.
    • Extract prefixes by incrementally appending characters (digits) from the string representation of each number.
    • Store each prefix in the map and count its occurrences.

  3. Checking Prefixes in the Second Array:

    • For each number in arr2, convert it to a string.
    • Build prefixes similarly to how it was done for arr1.
    • Check if any of these prefixes exist in the map from arr1. If found, update the maximum common prefix length.

  4. Result:

    • Return the maximum length of the common prefix found between arr1 and arr2.

Java Code Explanation

  1. Using a HashMap:

    • A HashMap is used to store the prefixes of the numbers from the first array (arr1).

  2. Storing Prefixes from arr1:

    • Convert each number from arr1 into a string.
    • Generate all possible prefixes by iterating over the string representation of the number and store them in the HashMap.
    • Each prefix is stored with its count (or incremented if it already exists).

  3. Searching in arr2:

    • For each number in arr2, generate its prefixes by converting the number to a string.
    • Check if any prefix exists in the HashMap from arr1. Update the maximum common prefix length if found.

  4. Final Step:

    • Return the longest common prefix length found.

JavaScript Code Explanation

  1. Prefix Map:

    • A Map is used to store the prefixes of the numbers from arr1.

  2. Prefix Generation for arr1:

    • Convert each number in arr1 to a string.
    • For each character (digit) in the string, append it to the growing prefix.
    • Add each prefix to the Map and increment its count if it already exists.

  3. Check for Common Prefixes in arr2:

    • For each number in arr2, convert it to a string and generate its prefixes.
    • Check if any of these prefixes exist in the Map. If found, update the length of the longest common prefix.

  4. Return the Result:

    • Return the maximum length of the common prefix found between arr1 and arr2.

Python Code Explanation

  1. Prefix Dictionary:

    • A dictionary (prefix_map) is used to store prefixes of numbers from arr1.

  2. Building the Prefix Map:

    • Convert each number from arr1 to a string.
    • Incrementally build prefixes by iterating through each character of the string.
    • Store the prefixes in the dictionary and count their occurrences.

  3. Check for Common Prefixes in arr2:

    • For each number in arr2, convert it to a string and generate prefixes.
    • Check if these prefixes exist in the dictionary from arr1 and update the longest common prefix length accordingly.

  4. Final Output:

    • Return the length of the longest common prefix found.

Go Code Explanation

  1. Prefix Map:

    • A map (prefixMap) is used to store prefixes of numbers from arr1 along with their counts.

  2. Building Prefixes for arr1:

    • Convert each number from arr1 to a string.
    • Incrementally build prefixes by iterating over the string.
    • Store these prefixes in the map and count their occurrences.

  3. Checking Prefixes in arr2:

    • Convert each number from arr2 to a string and generate prefixes similarly.
    • Check if these prefixes exist in the prefixMap. If found, update the longest common prefix length.

  4. Return Result:

    • The function returns the maximum length of the common prefix between the two arrays.

In summary, each language implements the same core algorithm:

  1. Build a map of prefixes from the first array.
  2. Check for common prefixes in the second array.
  3. Track and return the longest common prefix length found.