# LeetCode 165: Compare Version Numbers

## Problem Restatement

We are given two version strings:

```python
version1
version2
```

Each version string contains revisions separated by dots.

For example:

```python
"1.2.10"
```

has revisions:

```python
1, 2, 10
```

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

Return:

| Return value | Meaning |
|---|---|
| `-1` | `version1` is smaller |
| `1` | `version1` is larger |
| `0` | Both versions are equal |

Leading zeros are ignored, so:

```python
"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

| Item | Meaning |
|---|---|
| Input | Two strings `version1` and `version2` |
| Output | `-1`, `1`, or `0` |
| Separator | Dot character `"."` |
| Compare rule | Compare revisions as integers |
| Leading zeros | Ignored |
| Missing revisions | Treated as `0` |

Example function shape:

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

## Examples

Example 1:

```python
version1 = "1.2"
version2 = "1.10"
```

Compare revision by revision:

| Revision index | `version1` | `version2` |
|---|---:|---:|
| `0` | `1` | `1` |
| `1` | `2` | `10` |

The first revision is equal.

The second revision decides the answer:

```python
2 < 10
```

So the answer is:

```python
-1
```

Example 2:

```python
version1 = "1.01"
version2 = "1.001"
```

The second revisions are:

```python
"01"
"001"
```

Both have integer value:

```python
1
```

So the answer is:

```python
0
```

Example 3:

```python
version1 = "1.0"
version2 = "1.0.0.0"
```

The missing revisions in `version1` are treated as zero.

So both represent:

```python
1.0.0.0
```

The answer is:

```python
0
```

## First Thought: Split and Compare

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

```python
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:

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

Compute the maximum number of revisions:

```python
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:

```python
version1 = "1.0.1"
version2 = "1"
```

Split:

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

Compare index `0`:

```python
1 == 1
```

Compare index `1`:

```python
0 == 0
```

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

Compare index `2`:

```python
1 > 0
```

So return:

```python
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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Splitting and integer conversion scan the strings |
| Space | `O(n)` | Split arrays store the revisions |

## Implementation

```python
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:

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

Then compare enough positions to cover both versions:

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

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

```python
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:

```python
int("001")
```

gives:

```python
1
```

Then compare:

```python
if a < b:
    return -1

if a > b:
    return 1
```

If no difference is found:

```python
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.

```python
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

```python
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()
```

| Test | Why |
|---|---|
| `"1.2"`, `"1.10"` | Numeric comparison, not string comparison |
| `"1.01"`, `"1.001"` | Leading zeros ignored |
| `"1.0"`, `"1.0.0.0"` | Missing revisions treated as zero |
| `"1.0.1"`, `"1"` | Extra non-zero revision |
| `"0.1"`, `"1.1"` | Difference in first revision |
| `"1.0.0.1"`, `"1.0"` | Later revision decides |
| `"7.5.2.4"`, `"7.5.3"` | Middle revision decides |
| `"1.000000"`, `"1.0"` | Many leading zeros |