Compare Version Numbers – 165. LeetCode

To solve the Compare Version Numbers problem, we need to compare version strings like “1.0.0
and “1.0.1”. Each string is split by . to represent levels of the version, such as major.minor.patch. Our task is to compare these levels and determine which version is larger or if they are equal.

Optimal Algorithm Choice: Two-Pointer Approach

The most efficient solution uses a two-pointer approach where we traverse both version strings in parallel, comparing corresponding levels. This approach is optimal because:

1. Time Complexity: O(n + m) where n and m are the lengths of the two version strings. We make a single pass through each string.

2. Space Complexity: O(1) since we use only a few variables, with no extra data structures for storage.

Two-Pointer (Dual Iteration)

The two-pointer technique is ideal here as it allows us to compare the levels of both version numbers side-by-side in one pass. This pattern is frequently used in scenarios where we need to process two sequences simultaneously, making it suitable for problems that involve comparing lists, strings, or linked structures.

Steps of the Algorithm

1. Split Each Version: This creates an array where each element is a version level.
2. Compare Levels Using Two Pointers: For each corresponding level, convert it to an integer and compare.
3. Handle Uneven Lengths: If one version has fewer levels, treat the missing levels as 0.
4. Return Result: If a difference is found, return 1 or -1 depending on which is greater; otherwise, return 0 if all levels are equal.

public int compareVersion(String version1, String version2) {
    String[] levels1 = version1.split("\\.");
    String[] levels2 = version2.split("\\.");
    
    int maxLength = Math.max(levels1.length, levels2.length);
    
    for (int i = 0; i < maxLength; i++) {
        int v1 = i < levels1.length ? Integer.parseInt(levels1[i]) : 0;
        int v2 = i < levels2.length ? Integer.parseInt(levels2[i]) : 0;
        
        if (v1 < v2) return -1;
        if (v1 > v2) return 1;
    }
    
    return 0;
}

Explanation of the Code (Line-by-Line)

1. Split the Versions:

String[] levels1 = version1.split("\\.");
String[] levels2 = version2.split("\\.");

• We split each version string by “.”, creating an array where each element represent a version level. For example, “1.0.0” becomes [“1”, “0”, “0”].

2. Determine the Maximum Length:

int maxLength = Math.max(levels1.length, levels2.length);

• To handle different length (e.g. “1.0” vs “1.0.0), we find the maximum length of the two larrays. This lets us compare all levels, even if one version is shorter.

3. Loop Through Each Level:

for (int i = 0; i < maxLength; i++) {
    int v1 = i < levels1.length ? Integer.parseInt(levels1[i]) : 0;
    int v2 = i < levels2.length ? Integer.parseInt(levels2[i]) : 0;
}

• We iterate up to maxLength.

• For each level i, if it exists in levels1, we convert it to an integer (v1) otherwise, we set v1 to 0 (for cases like “1.0” which is treated as “1.0.0
• Similary, we do the same for levels2, setting v2 tp 0 if it doesn’t have a level at i.

4. Compare Each Level:

    if (v1 < v2) return -1;
    if (v1 > v2) return 1;

• We compare v1 and v2. If v1 is smaller, we return -1, indicating version1 is smaller. If v1 is greater, we return 1.

5. Return 0 if All Levels Are Equal:

return 0;

• If all levels are equal after the loop, we return 0, meaning the versions are the same.

Why This Algorithm?

The two-pointer approach allows us to handle each version’s levels directly without extra storage, keeping it efficient and simple. This pattern applies well to problems involving side-by-side comparisons, as in comparing parallel arrays or strings, and is efficient in scenarios where a single pass suffices.

This solution achieves the lowest time complexity possible for this problem and maintains constant space usage, aligning with the goal of clean, modern, and efficient code.