Compare Version Numbers

Description

165. Compare Version Numbers

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 fewer revisions, which means every missing revision is treated as "0".

Constraints:

• $1\le \text{version1.length},\text{version2.length}\le 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.

---

Approach 1: String Splitting ($O(N+M)$ Time, $O(N+M)$ Space)

Intuition

1. Split both version strings by "." into string arrays of individual revisions.
2. Iterate up to the maximum revision count between the two arrays.
3. Convert each revision string to an integer (which automatically strips leading zeros using Integer.parseInt). If an index exceeds an array’s length, default its value to 0.
4. Compare corresponding revision integers step-by-step. Return -1 or 1 on the first difference. If all revisions match, return 0.

class Solution {
    public int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
 
        int maxLength = Math.max(v1.length, v2.length);
 
        for (int i = 0; i < maxLength; i++) {
            int num1 = (i < v1.length) ? Integer.parseInt(v1[i]) : 0;
            int num2 = (i < v2.length) ? Integer.parseInt(v2[i]) : 0;
 
            if (num1 < num2) return -1;
            if (num1 > num2) return 1;
        }
 
        return 0;
    }
}
 

Complexity

• Time Complexity: $O(N+M)$ — Where $N$ and $M$ are the lengths of version1 and version2. Splitting and parsing take linear time.
• Space Complexity: $O(N+M)$ — To store the split string arrays in memory.

---

Approach 2: Two Pointers / On-the-Fly Parsing (Optimal — $O(\max (N,M))$ Time, $O(1)$ Space)

Intuition

Instead of creating arrays, parse numbers character-by-character using two pointers i and j moving through version1 and version2:

1. Parse digits until reaching a dot '.' or the end of the string to form the integer revision for each version.
2. Compare the two calculated numbers. If one is smaller/larger, return -1 or 1.
3. Advance both pointers past the dot '.' and repeat until both strings are completely traversed.

This eliminates string allocations completely.

class Solution {
    public int compareVersion(String version1, String version2) {
        int i = 0, j = 0;
        int n1 = version1.length(), n2 = version2.length();
 
        while (i < n1 || j < n2) {
            int num1 = 0;
            while (i < n1 && version1.charAt(i) != '.') {
                num1 = num1 * 10 + (version1.charAt(i) - '0');
                i++;
            }
 
            int num2 = 0;
            while (j < n2 && version2.charAt(j) != '.') {
                num2 = num2 * 10 + (version2.charAt(j) - '0');
                j++;
            }
 
            if (num1 < num2) return -1;
            if (num1 > num2) return 1;
 
            i++; // Skip '.' in version1
            j++; // Skip '.' in version2
        }
 
        return 0;
    }
}
 

Complexity

• Time Complexity: $O(\max (N,M))$ — Performs a single pass over both input strings.
• Space Complexity: $O(1)$ — Uses a few primitive variables with zero auxiliary heap allocations.

---

Easy Memory Rule

“Parse revision by revision between dots $\to$ compare integers $\to$ default missing revisions to 0!”