LeetCode 165: Compare Version Numbers Solution in Python Explained

Problem Statement

In LeetCode 165, you’re given two version strings version1 and version2, each a sequence of non-negative integers separated by dots (e.g., "1.2.3"). Your task is to compare them by their revisions from left to right, returning 1 if version1 > version2, -1 if version1 < version2, or 0 if equal. Trailing zeros after a dot are ignored (e.g., "1.0" = "1"). This differs from gap finding like LeetCode 164: Maximum Gap, focusing on string comparison rather than array differences.

Constraints

• 1 <= version1.length, version2.length <= 500
• Version strings contain digits and dots ('.')
• No leading zeros in revisions
• Valid version format

Example

Let’s see some cases:

Copy codeInput: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: "1.01" = "1.1" = "1.001" (trailing zeros ignored).

Copy codeInput: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: "1.0" = "1.0.0" (trailing zeros ignored).

Copy codeInput: version1 = "0.1", version2 = "1.1"
Output: -1
Explanation: 0.1 < 1.1 (first revision differs).

Copy codeInput: version1 = "1.0.1", version2 = "1"
Output: 1
Explanation: 1.0.1 > 1.0 (extra revision).

These examples show we’re comparing version revisions.

Understanding the Problem

How do you solve LeetCode 165: Compare Version Numbers in Python? Take version1 = "1.01", version2 = "1.001". Parse as [1,1] and [1,1], equal after ignoring trailing zeros, so return 0. For "0.1" vs "1.1", [0,1] < [1,1], return -1. For "1.0.1" vs "1", [1,0,1] > [1,0], return 1. We need to parse revisions efficiently, not a peak-finding task like LeetCode 162: Find Peak Element. We’ll use: 1. Two-Pointer Parsing: O(n) time, O(1) space—our best solution. 2. Split and Compare: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Two-Pointer Parsing Approach

Explanation

Two-Pointer Parsing uses pointers to traverse both strings, parsing revisions on-the-fly:

• For each string, use a pointer to track position.
• Extract numeric revisions between dots, comparing as integers.
• Handle unequal lengths by assuming trailing zeros.
• Return comparison result (-1, 0, 1).

This is the best solution due to its O(n) time complexity (n = max string length), O(1) space usage (no extra arrays), and efficiency by avoiding string splitting, making it optimal and elegant.

For "1.01" vs "1.001":

• Parse 1 vs 1, equal.
• Parse 1 vs 1, equal, both end, return 0.

Step-by-Step Example

Example 1: version1 = "1.01", version2 = "1.001"

Goal: Return 0.

• Start: i=0, j=0.
• Step 1: Parse first revision.
• v1=1, i=2, v2=1, j=2, equal.
• Step 2: Parse second revision.
• v1=1, i=5, v2=1, j=6, equal, both end.
• Finish: Return 0.

Example 2: version1 = "1.0", version2 = "1.0.0"

Goal: Return 0.

• Step 1: v1=1, v2=1, equal.
• Step 2: v1=0, v2=0, equal.
• Step 3: v1 ends, v2=0, equal, both end.
• Finish: Return 0.

Example 3: version1 = "0.1", version2 = "1.1"

Goal: Return -1.

• Step 1: v1=0, v2=1, 0 < 1, return -1.
• Finish: Return -1.

How the Code Works (Two-Pointer Parsing) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codedef compareVersion(version1: str, version2: str) -> int:
    # Line 1: Initialize pointers
    i = 0
    # Pointer for version1 (e.g., 0)
    j = 0
    # Pointer for version2 (e.g., 0)

    # Line 2: Parse and compare revisions
    while i < len(version1) or j < len(version2):
        # Continue until both strings processed (e.g., "1.01" vs "1.001")

        # Line 3: Parse revision from version1
        v1 = 0
        # Revision value (e.g., 0)
        while i < len(version1) and version1[i] != '.':
            # Extract number (e.g., "1")
            v1 = v1 * 10 + int(version1[i])
            i += 1
        i += 1  # Skip dot (e.g., i=2)

        # Line 4: Parse revision from version2
        v2 = 0
        # Revision value (e.g., 0)
        while j < len(version2) and version2[j] != '.':
            # Extract number (e.g., "1")
            v2 = v2 * 10 + int(version2[j])
            j += 1
        j += 1  # Skip dot (e.g., j=2)

        # Line 5: Compare revisions
        if v1 < v2:
            # v1 less (e.g., 0 < 1)
            return -1
        elif v1 > v2:
            # v1 greater (e.g., 1 > 0)
            return 1

    # Line 6: Return equal if all revisions match
    return 0
    # e.g., 0 for "1.01" vs "1.001"

This detailed breakdown clarifies how two-pointer parsing efficiently compares version numbers.

Alternative: Split and Compare Approach

Explanation

Split and Compare splits both strings into revision lists and compares them:

• Split version1 and version2 by dots into arrays.
• Convert each revision to an integer, padding shorter arrays with zeros.
• Compare revisions pairwise, returning -1, 0, or 1.

It’s a practical alternative, O(n) time (n = total characters), but uses O(n) space for the arrays, less space-efficient than parsing in-place.

For "1.01" vs "1.001":

• Split: [1,1] vs [1,1], equal, return 0.

Step-by-Step Example (Alternative)

For "0.1" vs "1.1":

• Step 1: Split: [0,1] vs [1,1].
• Step 2: Compare: 0 < 1, return -1.
• Finish: Return -1.

How the Code Works (Split and Compare)

Copy codedef compareVersionSplit(version1: str, version2: str) -> int:
    v1 = [int(x) for x in version1.split('.')]
    v2 = [int(x) for x in version2.split('.')]

    len1, len2 = len(v1), len(v2)
    for i in range(max(len1, len2)):
        r1 = v1[i] if i < len1 else 0
        r2 = v2[i] if i < len2 else 0
        if r1 < r2:
            return -1
        elif r1 > r2:
            return 1
    return 0

Complexity

• Two-Pointer Parsing:
• Time: O(n) – single pass over strings.
• Space: O(1) – constant space.
• Split and Compare:
• Time: O(n) – splitting and comparison.
• Space: O(n) – revision arrays.

Efficiency Notes

Two-Pointer Parsing is the best solution with O(n) time and O(1) space, offering efficiency and minimal memory—Split and Compare matches time complexity but uses O(n) space due to arrays, making it simpler but less space-efficient.

Key Insights

• Parsing: In-place efficiency.
• Splitting: Array convenience.
• Revisions: Compare numerically.

Additional Example

For version1 = "1.2", version2 = "1.10":

• Goal: -1.
• Two-Pointer: 1=1, 2<10, return -1.

Edge Cases

• Equal: "1", "1.0" → 0.
• Short: "1", "1.1" → -1.
• Long: "1.0.0", "1" → 0.

Both solutions handle these well.

Final Thoughts

LeetCode 165: Compare Version Numbers in Python is a practical string comparison challenge. The Two-Pointer Parsing solution excels with its efficiency and elegance, while Split and Compare offers a straightforward approach. Want more? Try LeetCode 161: One Edit Distance for string edits or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 165 on LeetCode with "1.01" and "1.001", aiming for 0—test your skills now!