LeetCode 165 - Compare Version Numbers

This problem asks us to compare two software version numbers represented as strings. Each version consists of one or more numeric revisions separated by dots (.). For example, "1.2.10" contains three revisions: 1, 2, and 10.

leetcodemediumtwo-pointersstring

LeetCode Problem 165

Difficulty: 🟡 Medium
Topics: Two Pointers, String

Solution

Problem Understanding

This problem asks us to compare two software version numbers represented as strings. Each version consists of one or more numeric revisions separated by dots (.). For example, "1.2.10" contains three revisions: 1, 2, and 10.

The important detail is that revisions are compared as integers, not strings. This means leading zeros must be ignored. For example, "01" and "001" both represent the integer 1, so they are considered equal.

The comparison must happen from left to right, revision by revision. At each position:

  • If the revision in version1 is smaller than the corresponding revision in version2, return -1.
  • If it is larger, return 1.
  • If they are equal, continue comparing the next revision.

Another important rule is that missing revisions are treated as 0. For example:

  • "1.0" and "1.0.0.0" are equal because the missing revisions in "1.0" behave like zeros.
  • "1.2" is smaller than "1.2.1" because the missing third revision in "1.2" is treated as 0.

The input size is relatively small, with each version string having length at most 500. Since every revision fits inside a 32-bit integer, we do not need to worry about parsing extremely large numeric values. This means an efficient linear scan solution is more than sufficient.

There are several edge cases that can easily trip up a naive implementation. Leading zeros are one such case, because string comparison would incorrectly consider "01" and "1" different. Versions with different numbers of revisions are another challenge, because trailing missing revisions must be interpreted as zero. Finally, trailing zero revisions such as "1.0.0" versus "1" must be handled correctly and treated as equal.

Approaches

Brute Force Approach

A straightforward solution is to split both version strings by dots into arrays of strings, convert every revision to integers, and then compare them index by index.

For example:

"1.02.10" → [1, 2, 10]
"1.2.3"   → [1, 2, 3]

We would iterate through the longer array length and treat any missing elements as 0.

This approach is correct because it directly follows the problem definition. Every revision is normalized into its integer representation, leading zeros are naturally removed during integer conversion, and missing revisions become zero.

However, splitting the strings creates additional arrays and temporary string objects. While the constraints are small enough that this still works efficiently, we can do better in terms of auxiliary space.

Key Insight

We do not actually need to split the version strings into arrays.

Instead, we can process both strings using two pointers and parse each revision on the fly. Since revisions are separated by dots, we can scan until the next dot, build the integer value, compare it, and move forward.

This works because version comparison is inherently sequential. We only care about one revision pair at a time. There is no need to store all revisions beforehand.

This gives us an optimal linear solution with constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n + m) O(n + m) Split strings into arrays and compare revisions
Optimal O(n + m) O(1) Two pointers parse revisions directly without extra storage

Here, n and m are the lengths of version1 and version2.

Algorithm Walkthrough

Optimal Two Pointer Algorithm

  1. Initialize two pointers, one for each version string.

These pointers track the current parsing position in version1 and version2. Since revisions are processed left to right, pointers allow us to scan efficiently without splitting. 2. While either pointer has not reached the end of its string, extract the next revision number.

For each version:

  • Start with revision = 0.
  • Read digits until reaching a dot (.) or the end of the string.
  • Convert the revision into an integer by repeatedly multiplying by 10 and adding the digit.

This automatically ignores leading zeros because integer construction normalizes them. 3. Compare the extracted revisions.

  • If revision1 < revision2, return -1.
  • If revision1 > revision2, return 1.

If they are equal, continue to the next revision. 4. Move pointers past the dot separator.

After processing a revision, increment the pointer once more to skip the dot if it exists. 5. Continue until both strings are fully processed.

If no difference was found, return 0 because all revisions matched.

Why it works

The algorithm maintains the invariant that every revision before the current pointers has already been correctly compared and found equal. At each step, it compares exactly one corresponding revision pair according to the problem rules. Missing revisions naturally become 0 because once a pointer reaches the end of its string, its parsed revision remains zero. Since every revision is processed in order and any unequal revision immediately determines the result, the algorithm is guaranteed to return the correct comparison.

Python Solution

class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        pointer1 = 0
        pointer2 = 0

        length1 = len(version1)
        length2 = len(version2)

        while pointer1 < length1 or pointer2 < length2:
            revision1 = 0
            revision2 = 0

            while pointer1 < length1 and version1[pointer1] != ".":
                revision1 = revision1 * 10 + int(version1[pointer1])
                pointer1 += 1

            while pointer2 < length2 and version2[pointer2] != ".":
                revision2 = revision2 * 10 + int(version2[pointer2])
                pointer2 += 1

            if revision1 < revision2:
                return -1

            if revision1 > revision2:
                return 1

            pointer1 += 1
            pointer2 += 1

        return 0

The implementation begins by creating two pointers that track positions in the version strings. Instead of splitting the strings, the algorithm reads revisions directly.

Inside the main loop, each revision is parsed character by character until reaching a dot or the end of the string. Multiplying the current value by 10 and adding the next digit constructs the integer representation naturally, which also removes any leading zeros.

After both revisions are extracted, they are immediately compared. If one is larger, the answer is returned right away because version comparison is determined by the first differing revision.

If the revisions are equal, the pointers advance past the dot separator and continue processing the next revision. If the loop finishes without finding a difference, the versions are equal and 0 is returned.

Go Solution

func compareVersion(version1 string, version2 string) int {
    pointer1 := 0
    pointer2 := 0

    length1 := len(version1)
    length2 := len(version2)

    for pointer1 < length1 || pointer2 < length2 {
        revision1 := 0
        revision2 := 0

        for pointer1 < length1 && version1[pointer1] != '.' {
            revision1 = revision1*10 + int(version1[pointer1]-'0')
            pointer1++
        }

        for pointer2 < length2 && version2[pointer2] != '.' {
            revision2 = revision2*10 + int(version2[pointer2]-'0')
            pointer2++
        }

        if revision1 < revision2 {
            return -1
        }

        if revision1 > revision2 {
            return 1
        }

        pointer1++
        pointer2++
    }

    return 0
}

The Go implementation follows the same two pointer strategy as the Python solution. Since Go strings are byte slices internally, digit conversion is performed using:

int(version1[pointer1] - '0')

This converts a character digit into its numeric value efficiently.

No special overflow handling is needed because the problem guarantees every revision fits inside a 32-bit integer. Missing revisions are naturally treated as zero because once a pointer reaches the end of a string, its revision value remains 0.

Worked Examples

Example 1

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

Step revision1 revision2 Comparison Result
First revision 1 1 Equal Continue
Second revision 2 10 2 < 10 Return -1

Final output:

-1

Example 2

Input: version1 = "1.01", version2 = "1.001"

Step revision1 revision2 Comparison Result
First revision 1 1 Equal Continue
Second revision 1 1 Equal Continue
End - - No differences Return 0

Notice that "01" and "001" both become integer 1.

Final output:

0

Example 3

Input: version1 = "1.0", version2 = "1.0.0.0"

Step revision1 revision2 Comparison Result
First revision 1 1 Equal Continue
Second revision 0 0 Equal Continue
Third revision 0 0 Missing revision treated as 0 Continue
Fourth revision 0 0 Missing revision treated as 0 Continue
End - - No differences Return 0

Final output:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each character in both strings is processed at most once
Space O(1) Only a few integer variables and pointers are used

The time complexity is linear because each pointer moves through its version string exactly once. No character is revisited, making the total work proportional to the combined input size.

The space complexity is constant because we only maintain a handful of variables regardless of input length. No auxiliary arrays or split results are created.

Test Cases

solution = Solution()

assert solution.compareVersion("1.2", "1.10") == -1  # smaller second revision
assert solution.compareVersion("1.01", "1.001") == 0  # leading zeros ignored
assert solution.compareVersion("1.0", "1.0.0.0") == 0  # trailing missing revisions

assert solution.compareVersion("1", "1.0") == 0  # missing revision treated as zero
assert solution.compareVersion("1.0.1", "1") == 1  # later revision larger
assert solution.compareVersion("1.0", "1.0.1") == -1  # later revision smaller

assert solution.compareVersion("0.1", "1.1") == -1  # smaller first revision
assert solution.compareVersion("2.0", "1.9.9") == 1  # larger first revision

assert solution.compareVersion("1.000000", "1") == 0  # many leading zeros
assert solution.compareVersion("3.5.7", "3.5.7") == 0  # identical versions

assert solution.compareVersion("10.2", "2.10") == 1  # integer comparison, not string comparison
assert solution.compareVersion("1.100", "1.99") == 1  # multi-digit revision comparison

assert solution.compareVersion("0", "0.0.0") == 0  # all zero revisions
assert solution.compareVersion("500", "499.999") == 1  # large revision values
Test Why
"1.2" vs "1.10" Validates numeric comparison of revisions
"1.01" vs "1.001" Ensures leading zeros are ignored
"1.0" vs "1.0.0.0" Confirms missing revisions become zero
"1" vs "1.0" Tests equality with trailing zeros
"1.0.1" vs "1" Verifies later revision determines result
"1.0" vs "1.0.1" Tests missing revision treated as zero
"0.1" vs "1.1" Ensures first unequal revision decides outcome
"2.0" vs "1.9.9" Tests early termination on larger first revision
"1.000000" vs "1" Confirms many leading zeros work correctly
"3.5.7" vs "3.5.7" Tests exact equality
"10.2" vs "2.10" Prevents incorrect lexicographic comparison
"1.100" vs "1.99" Verifies multi-digit integer comparison
"0" vs "0.0.0" Handles all-zero revisions
"500" vs "499.999" Tests larger revision values

Edge Cases

One important edge case is leading zeros in revisions. A naive string comparison might incorrectly decide that "01" and "1" are different because their textual forms differ. The implementation avoids this issue by parsing revisions as integers, which automatically removes leading zeros during conversion.

Another critical edge case is versions with different lengths. For example, "1.0" and "1.0.0.0" should be equal. A naive implementation that stops once one string ends might incorrectly conclude they differ. The algorithm handles this correctly by continuing until both strings are exhausted and treating missing revisions as 0.

A third subtle edge case is multi-digit numeric comparison versus lexicographic comparison. Consider "1.10" and "1.2". String comparison would incorrectly say "10" < "2" because '1' < '2'. Since the implementation constructs integer values, it correctly evaluates 10 > 2.

Finally, all-zero trailing revisions such as "0" versus "0.0.0" can cause mistakes if trailing revisions are not normalized. Because missing revisions default to 0, the implementation correctly identifies these versions as equal.