LeetCode 165: Compare Version Numbers

Problem Restatement

We are given two version strings:

version1
version2

Each version string contains revisions separated by dots.

For example:

"1.2.10"

has revisions:

1, 2, 10

We need to compare the two versions revision by revision from left to right.

Return:

Leading zeros are ignored, so:

"1.01"
"1.001"

are equal.

If one version has fewer revisions, the missing revisions are treated as 0. For example, "1.0" and "1.0.0.0" are equal. LeetCode states that both version strings are valid, contain only digits and dots, and each revision fits in a 32-bit integer.

Input and Output

Example function shape:

def compareVersion(version1: str, version2: str) -> int:
    ...

Examples

Example 1:

version1 = "1.2"
version2 = "1.10"

Compare revision by revision:

The first revision is equal.

The second revision decides the answer:

2 < 10

So the answer is:

-1

Example 2:

version1 = "1.01"
version2 = "1.001"

The second revisions are:

"01"
"001"

Both have integer value:

1

So the answer is:

0

Example 3:

version1 = "1.0"
version2 = "1.0.0.0"

The missing revisions in version1 are treated as zero.

So both represent:

1.0.0.0

The answer is:

0

First Thought: Split and Compare

The most direct solution is to split both strings by ".".

parts1 = version1.split(".")
parts2 = version2.split(".")

Then compare each revision as an integer.

If one list runs out of revisions, use 0.

This is simple and accepted.

Algorithm

Split both versions:

parts1 = version1.split(".")
parts2 = version2.split(".")

Compute the maximum number of revisions:

m = max(len(parts1), len(parts2))

For each index i from 0 to m - 1:

1. Read revision i from parts1, or use 0 if missing.
2. Read revision i from parts2, or use 0 if missing.
3. Convert both revisions to integers.
4. If the first is smaller, return -1.
5. If the first is larger, return 1.

If all revisions match, return 0.

Walkthrough

Use:

version1 = "1.0.1"
version2 = "1"

Split:

parts1 = ["1", "0", "1"]
parts2 = ["1"]

Compare index 0:

1 == 1

Compare index 1:

0 == 0

The second version has no revision at index 1, so we use 0.

Compare index 2:

1 > 0

So return:

1

Correctness

The problem defines version comparison as left-to-right comparison of integer revision values.

The algorithm constructs exactly those revision values by splitting on dots and converting each revision to an integer. This conversion removes leading zeros automatically.

For any revision index that is missing from one version, the algorithm uses 0, matching the rule that missing revisions are treated as zero.

At the first index where the two revision values differ, the version with the larger revision is larger by definition, so returning 1 or -1 is correct.

If no revision differs, every specified and missing revision has equal integer value. Therefore, the two versions are equal, and returning 0 is correct.

Complexity

Let n be the total length of both version strings.

Implementation

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        parts1 = version1.split(".")
        parts2 = version2.split(".")

        m = max(len(parts1), len(parts2))

        for i in range(m):
            a = int(parts1[i]) if i < len(parts1) else 0
            b = int(parts2[i]) if i < len(parts2) else 0

            if a < b:
                return -1

            if a > b:
                return 1

        return 0

Code Explanation

Split both versions into revisions:

parts1 = version1.split(".")
parts2 = version2.split(".")

Then compare enough positions to cover both versions:

m = max(len(parts1), len(parts2))

For each position, use the real revision if it exists, otherwise use zero:

a = int(parts1[i]) if i < len(parts1) else 0
b = int(parts2[i]) if i < len(parts2) else 0

Integer conversion handles leading zeros.

For example:

int("001")

gives:

1

Then compare:

if a < b:
    return -1

if a > b:
    return 1

If no difference is found:

return 0

the versions are equal.

Two-Pointer Implementation

We can avoid storing split arrays by parsing each revision directly.

This uses constant extra space.

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        i = 0
        j = 0
        m = len(version1)
        n = len(version2)

        while i < m or j < n:
            a = 0
            while i < m and version1[i] != ".":
                a = a * 10 + int(version1[i])
                i += 1

            b = 0
            while j < n and version2[j] != ".":
                b = b * 10 + int(version2[j])
                j += 1

            if a < b:
                return -1

            if a > b:
                return 1

            i += 1
            j += 1

        return 0

This version treats missing revisions as zero because once a pointer reaches the end, its parsed value stays 0 for remaining iterations.

Testing

def run_tests():
    sol = Solution()

    assert sol.compareVersion("1.2", "1.10") == -1
    assert sol.compareVersion("1.01", "1.001") == 0
    assert sol.compareVersion("1.0", "1.0.0.0") == 0
    assert sol.compareVersion("1.0.1", "1") == 1
    assert sol.compareVersion("0.1", "1.1") == -1
    assert sol.compareVersion("1.0.0.1", "1.0") == 1
    assert sol.compareVersion("7.5.2.4", "7.5.3") == -1
    assert sol.compareVersion("1.000000", "1.0") == 0

    print("all tests passed")

run_tests()