# Compare Version Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/compare-version-numbers)
Canonical: https://scaleengineer.com/dsa/problems/compare-version-numbers
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [TikTok](https://scaleengineer.com/companies/tiktok), [Zoho](https://scaleengineer.com/companies/zoho), [Nextdoor](https://scaleengineer.com/companies/nextdoor)
---
## Problem
Given two **version strings**, `version1` and `version2`, compare them. A version string consists of **revisions** separated by dots `'.'`. The **value of the revision** is its **integer conversion** ignoring leading zeros.

To compare version strings, compare their revision values in **left-to-right order**. If one of the version strings has fewer revisions, treat the missing revision values as `0`.

Return the following:

* If `version1 < version2`, return -1.
* If `version1 > version2`, return 1.
* Otherwise, return 0.

**Example 1:**

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

**Output:** \-1

**Explanation:**

version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

**Example 2:**

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

**Output:** 0

**Explanation:**

Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

**Example 3:**

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

**Output:** 0

**Explanation:**

version1 has less revisions, which means every missing revision are treated as "0".

**Constraints:**

* `1 <= version1.length, version2.length <= 500`
* `version1` and `version2` only contain digits and `'.'`.
* `version1` and `version2` **are valid version numbers**.
* All the given revisions in `version1` and `version2` can be stored in a **32-bit integer**.

# Approaches
## Split and Parse
This approach involves splitting the two version strings by the dot delimiter to get arrays of revision numbers. Then, it iterates through these arrays, comparing corresponding revision numbers. If one version has fewer revisions, they are treated as zeros.
**Time:** O(N + M) · **Space:** O(N + M)
**Pros:** Conceptually simple and straightforward to implement.; Effectively uses built-in language features for string manipulation and parsing.
**Cons:** Requires extra memory to store the arrays of revision strings, which can be significant if the version strings are long.
### Explanation
The core idea is to break down the problem into simpler parts: splitting the strings, parsing the numbers, and then comparing them.

- First, we use the `split` method with the regular expression `"\\."` to divide `version1` and `version2` into arrays of strings, where each string represents a revision.
- We then determine the maximum number of revisions between the two versions to set the boundary for our comparison loop.
- We iterate from the first revision (`i=0`) up to the maximum length. In each iteration:
    - We retrieve the `i`-th revision for both versions. If `i` exceeds the number of revisions for a version string, we treat its revision value as `0`.
    - We parse the string revisions into integers. `Integer.parseInt()` conveniently handles any leading zeros.
    - We compare the two integer revision values. If they are not equal, we have found the result and can return `1` or `-1` immediately.
- If the loop completes without returning, it means all revisions are equal (including the implicit trailing zeros), so we return `0`.

```java
class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1Revisions = version1.split("\\.");
        String[] v2Revisions = version2.split("\\.");
        
        int length1 = v1Revisions.length;
        int length2 = v2Revisions.length;
        int maxLength = Math.max(length1, length2);
        
        for (int i = 0; i < maxLength; i++) {
            int rev1 = (i < length1) ? Integer.parseInt(v1Revisions[i]) : 0;
            int rev2 = (i < length2) ? Integer.parseInt(v2Revisions[i]) : 0;
            
            if (rev1 < rev2) {
                return -1;
            }
            if (rev1 > rev2) {
                return 1;
            }
        }
        
        return 0;
    }
}
```
### Algorithm
- Split `version1` string by `.` into an array `v1Revisions`.
- Split `version2` string by `.` into an array `v2Revisions`.
- Find the maximum length between `v1Revisions` and `v2Revisions`, let's call it `maxLength`.
- Iterate from `i = 0` to `maxLength - 1`.
- Get the `i`-th revision for `version1`. If `i` is out of bounds, the revision is `0`. Otherwise, parse the string revision to an integer.
- Get the `i`-th revision for `version2`. If `i` is out of bounds, the revision is `0`. Otherwise, parse the string revision to an integer.
- Compare the two integer revisions. If `rev1 < rev2`, return `-1`. If `rev1 > rev2`, return `1`.
- If the loop finishes, it means all revisions are equal. Return `0`.

## Two Pointers / One Pass
This is a more optimized approach that avoids the overhead of splitting the strings and creating intermediate arrays. It uses two pointers to iterate through the version strings simultaneously, parsing the revision numbers on the fly and comparing them in a single pass.
**Time:** O(N + M) · **Space:** O(1)
**Pros:** Highly efficient in terms of memory usage, as it operates in constant extra space.; Processes the strings in a single pass, which can be faster in practice by avoiding the overhead of creating intermediate data structures.
**Cons:** The implementation logic is slightly more complex than the split-and-parse approach due to manual parsing and pointer management.
### Explanation
This method processes both strings in one go, maintaining a pointer for each string to keep track of the current position.

- We initialize two pointers, `p1` and `p2`, to the start of `version1` and `version2`.
- The main loop continues as long as we haven't reached the end of both strings (`p1 < n1` or `p2 < n2`).
- Inside the loop, for each version string, we have a nested loop that reads characters until a dot `.` is encountered or the end of the string is reached. While reading, we construct the integer value of the current revision. For example, for "123", we do `rev = 0 * 10 + 1`, then `rev = 1 * 10 + 2`, then `rev = 12 * 10 + 3`.
- After parsing a revision number from each string (or `0` if one pointer is already at the end), we compare them.
- If `rev1 > rev2`, we return `1`. If `rev1 < rev2`, we return `-1`.
- If they are equal, we advance both main pointers (`p1` and `p2`) past the dot to start parsing the next revision in the next iteration.
- If the main loop completes, it means all revisions were equal, and we return `0`.

```java
class Solution {
    public int compareVersion(String version1, String version2) {
        int p1 = 0, p2 = 0;
        int n1 = version1.length(), n2 = version2.length();
        
        while (p1 < n1 || p2 < n2) {
            int rev1 = 0;
            while (p1 < n1 && version1.charAt(p1) != '.') {
                rev1 = rev1 * 10 + (version1.charAt(p1) - '0');
                p1++;
            }
            
            int rev2 = 0;
            while (p2 < n2 && version2.charAt(p2) != '.') {
                rev2 = rev2 * 10 + (version2.charAt(p2) - '0');
                p2++;
            }
            
            if (rev1 > rev2) {
                return 1;
            } else if (rev1 < rev2) {
                return -1;
            }
            
            // Move past the dot
            p1++;
            p2++;
        }
        
        return 0;
    }
}
```
### Algorithm
- Initialize two pointers, `p1` for `version1` and `p2` for `version2`, both to `0`.
- Loop as long as `p1` is less than `version1`'s length or `p2` is less than `version2`'s length.
- Inside the loop, parse the next revision number from `version1` starting at `p1`. Iterate from `p1` until a `.` or the end of the string is found, calculating the integer value. Update `p1` to the position after the parsed number.
- Similarly, parse the next revision number from `version2` starting at `p2` and update `p2`.
- Compare the two parsed revision numbers. If `rev1 > rev2`, return `1`. If `rev1 < rev2`, return `-1`.
- After comparison, advance both pointers by one to skip the `.` character.
- If the loop completes, return `0`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int CompareVersion(string version1, string version2) {
        int m = version1.Length, n = version2.Length;
        for (int i = 0, j = 0; i < m || j < n; ++i, ++j) {
            int a = 0, b = 0;
            while (i < m && version1[i] != '.') {
                a = a * 10 + (version1[i++] - '0');
            }
            while (j < n && version2[j] != '.') {
                b = b * 10 + (version2[j++] - '0');
            }
            if (a != b) {
                return a < b ? -1 : 1;
            }
        }
        return 0;
    }
}
```

### Java

```java
class Solution {
public
  int compareVersion(String version1, String version2) {
    int m = version1.length(), n = version2.length();
    for (int i = 0, j = 0; i < m || j < n; ++i, ++j) {
      int a = 0, b = 0;
      while (i < m && version1.charAt(i) != '.') {
        a = a * 10 + (version1.charAt(i++) - '0');
      }
      while (j < n && version2.charAt(j) != '.') {
        b = b * 10 + (version2.charAt(j++) - '0');
      }
      if (a != b) {
        return a < b ? -1 : 1;
      }
    }
    return 0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int compareVersion(string version1, string version2) {
    int m = version1.size(), n = version2.size();
    for (int i = 0, j = 0; i < m || j < n; ++i, ++j) {
      int a = 0, b = 0;
      while (i < m && version1[i] != '.') {
        a = a * 10 + (version1[i++] - '0');
      }
      while (j < n && version2[j] != '.') {
        b = b * 10 + (version2[j++] - '0');
      }
      if (a != b) {
        return a < b ? -1 : 1;
      }
    }
    return 0;
  }
};

```

### Python

```python
class Solution:
    def compareVersion(self, version1: str, version2: str) -> int: m, n = len(version1), len(version2) i = j = 0 while i < m or j < n: a = b = 0 while i < m and version1[i] != '.': a = a * 10 + int(version1[i]) i += 1 while j < n and version2[j] != '.': b = b * 10 + int(version2[j]) j += 1 if a != b: return - 1 if a < b else 1 i, j = i + 1, j + 1 return 0

```