Compare Version Numbers — Solution in Python, Java & C++
Compare Version Numbers solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Compare Version Numbers is a medium coding problem on strings and two pointers.
- Difficulty: Medium
- Topics: Strings, Two Pointers
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two version strings, version1 and version2 (dot-separated numeric revisions, possibly with leading zeros), compare them.
Return -1 if version1 < version2, 1 if version1 > version2, otherwise 0. Missing revisions count as 0.
Example 1
Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation: Revision 2 < revision 10.
Example 2
Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Leading zeros are ignored.
Example 3
Input: version1 = "1.0", version2 = "1.0.0.0"
Output: 0
Constraints
1 <= version.length <= 20Only digits and '.'
Hints for Compare Version Numbers
Hint 1
Split on '.' and compare revision integers left to right.
Hint 2
When one version runs out of revisions, treat the rest as zeros.
How to solve Compare Version Numbers
Versions compare revision by revision numerically, not as text. Split both on dots, convert each revision to an integer — which discards leading zeros automatically — and walk them in parallel, treating a missing revision as 0 so "1.0" and "1.0.0.0" come out equal.
Approach
- Split both versions on
.. - Walk positions up to the longer of the two lists.
- Take each side's revision as an integer, or
0when that side has run out. - Return
-1or1at the first difference. - If every position matches, return
0.
Why it works
Numeric conversion is what makes "1.10" sort above "1.2" — lexicographic comparison would get that backwards — and it makes "01" and "1" identical without any explicit trimming. Padding the shorter version with zeros is the right semantics because trailing zero revisions carry no information, so "1.0" and "1.0.0.0" denote the same release.
Complexity
- Time —
O(|version1| + |version2|) - Space —
O(number of revisions)
Pitfalls
- String comparison is wrong:
"10" < "2"lexicographically but10 > 2numerically. - Missing revisions default to
0, so the walk must extend to the longer list rather than stopping at the shorter one. - Leading zeros are insignificant, which numeric conversion handles for free.
- Return exactly
-1,0or1, not the raw difference of the revisions.
Reference solution
Python
def compareVersion(version1: str, version2: str) -> int:
a = [int(x) for x in version1.split(".")]
b = [int(x) for x in version2.split(".")]
n = max(len(a), len(b))
for i in range(n):
x = a[i] if i < len(a) else 0
y = b[i] if i < len(b) else 0
if x < y:
return -1
if x > y:
return 1
return 0Java
public static int compareVersion(String version1, String version2) {
String[] a = version1.split("\\.");
String[] b = version2.split("\\.");
int n = Math.max(a.length, b.length);
for (int i = 0; i < n; i++) {
int x = i < a.length ? Integer.parseInt(a[i]) : 0;
int y = i < b.length ? Integer.parseInt(b[i]) : 0;
if (x < y) return -1;
if (x > y) return 1;
}
return 0;
}C++
int compareVersion(string version1, string version2) {
size_t i = 0, j = 0;
int n1 = (int) version1.size(), n2 = (int) version2.size();
while (i < (size_t) n1 || j < (size_t) n2) {
int x = 0, y = 0;
while (i < (size_t) n1 && version1[i] != '.') {
x = x * 10 + (version1[i] - '0');
i++;
}
while (j < (size_t) n2 && version2[j] != '.') {
y = y * 10 + (version2[j] - '0');
j++;
}
if (x < y) return -1;
if (x > y) return 1;
i++;
j++;
}
return 0;
}JavaScript
var compareVersion = function(version1, version2) {
const a = version1.split(".").map(Number);
const b = version2.split(".").map(Number);
const n = Math.max(a.length, b.length);
for (let i = 0; i < n; i++) {
const x = a[i] || 0, y = b[i] || 0;
if (x < y) return -1;
if (x > y) return 1;
}
return 0;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Two Pointers Technique