Compare Version Numbers
Problem statement
You're given two version strings, version1 and version2. Each one is a sequence of numbers (called revisions) separated by dots, like "1.2.10". Decide which version is "bigger" — the same way you'd compare two software release numbers by eye.
Compare the revisions in order, left to right, treating each one as a plain integer (so "01" and "1" are the same revision — leading zeros don't count). If one version has fewer revisions than the other, treat every missing revision on the shorter side as 0 — so "1.0" and "1.0.0" are considered equal.
Return -1 if version1 is smaller, 1 if it's bigger, and 0 if they're equal.
This is the exact comparison you'd want when deciding whether an installed package satisfies a ">= 2.4.0" constraint, or whether a deploy is rolling forward or backward between two release tags.
Examples
Example 1
Input: version1 = "1.2", version2 = "1.10"
Output: -1
Explanation: The first revisions (1 vs 1) are equal. The second revisions are 2 vs 10 — and as numbers, 2 is less than 10, even though "2" would sort after "10" as plain text.
Example 2
Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: "01" and "001" both represent the integer 1 once you drop the leading zeros, so every revision matches.
Example 3
Input: version1 = "1.0", version2 = "1.0.0.0"
Output: 0
Explanation: version1 has only 2 revisions; the missing 3rd and 4th revisions are treated as 0, which matches version2 exactly.
Hints
Approach
Optimal: Two pointers, no split
Intuition
Splitting both strings up front builds two full lists of revisions before any comparison happens, even though most of the time only the first one or two revisions actually differ. This approach reads one revision from each string at a time — walking a pointer forward through the digits until it hits a dot or the end of the string — compares that pair immediately, and can return the moment it finds a difference, without ever materializing the rest of either version.
Steps
- Start two pointers,
iandj, at the beginning ofversion1andversion2. - While either pointer still has characters left to read:
- Build up one revision's integer value from
version1by reading digits starting atiuntil a.or the end of the string, then moveipast the dot. - Do the same for
version2starting atj. - If a pointer has already run off the end of its string, that "revision" is simply
0(the inner digit-reading loop does nothing). - Compare the two integers; if they differ, return
-1or1right away.
- Build up one revision's integer value from
- If the loop finishes with every revision equal, return
0.
Dry run
version1 = "1.10", version2 = "1.2" (same digits as example 1, reversed), tracing the two pointers:
| round | version1 revision (from i) | version2 revision (from j) | compare |
|---|---|---|---|
| 1 | 1 (i moves 0→1, skips dot to 2) | 1 (j moves 0→1, skips dot to 2) | equal |
| 2 | 10 (i moves 2→4, end of string) | 2 (j moves 2→3, end of string) | 10 > 2 → return 1 |
Edge cases: once i reaches the end of version1 but j still has characters left in version2, the inner loop for version1 immediately finds no digits to read and produces 0 — exactly the "missing revision counts as 0" rule, without ever needing a separate length check.
Complexity
Time O(n + m) - Same total work as the split-based version: each character of both strings is visited exactly once as the two pointers sweep forward.
Space O(1) - extra — No list of revisions is ever built; only a handful of integer variables and the two pointer positions are kept.
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
n1, n2 = len(version1), len(version2)
i = j = 0
while i < n1 or j < n2:
v1 = 0
while i < n1 and version1[i] != '.':
v1 = v1 * 10 + int(version1[i])
i += 1
v2 = 0
while j < n2 and version2[j] != '.':
v2 = v2 * 10 + int(version2[j])
j += 1
if v1 < v2:
return -1
if v1 > v2:
return 1
i += 1 # skip the dot
j += 1
return 0
if __name__ == "__main__":
s = Solution()
print(s.compareVersion("1.2", "1.10")) # -1
print(s.compareVersion("1.01", "1.001")) # 0
print(s.compareVersion("1.0", "1.0.0.0")) # 0RecapThe whole problem in a few lines, for the night before
- Spot it: comparing two dot-separated "version"-style strings numerically, not as text
- Idea: split (or scan) into revisions, convert each to an integer, compare left to right, and treat a missing revision as 0
- Cost: O(n + m) time, O(n + m) space with splitting (O(1) extra with a two-pointer scan)
- Trap: comparing the raw strings character by character breaks as soon as a revision reaches two digits (
"2"vs"10") — always convert to a number first
Interview follow-ups
What if a revision could be negative, or the strings could contain non-digit, non-dot characters?
The problem guarantees valid input, but if that guarantee were relaxed, you'd add a validation pass before comparing — check every character in each revision is a digit, and decide up front how a negative sign or letter should be handled (reject the input, or treat it as part of an extended, project-specific version scheme). The comparison logic itself would stay the same once each revision is validated and parsed.
How would you compare versions like
"1.0.0-beta"that mix numbers with a suffix?Split off the suffix first (everything after the last dot, or after a
-), compare the pure numeric part with this same algorithm, and only fall back to comparing suffixes as a tiebreaker if the numeric parts are equal — with a rule for what a suffix like"beta"means relative to no suffix at all (usually: a version with a pre-release suffix is considered smaller than the same version without one).You need to sort a list of thousands of version strings, not just compare two at a time.
Reuse this exact comparison function as a custom comparator passed to a standard sort — most languages' sort functions accept a "compare these two items" callback, so nothing about the version-comparison logic needs to change. Sorting
kversions this way costs O(k log k) comparisons, each one still O(n + m) for the lengths involved, rather than writing a separate parsing pass for the whole list.
Frequently asked questions
Plain string comparison works character by character, and '2' comes after '1' in that ordering, so "1.2" would look bigger than "1.10" even though 2 < 10 numerically. Any comparison of version numbers has to treat each dot-separated piece as an integer, not as text, or multi-digit revisions break as soon as one revision reaches double digits.
int("001") and int("1") both evaluate to the plain number 1 — the conversion itself discards leading zeros, since they don't change the value being represented. That's exactly the rule the problem asks for, so there's no separate "strip leading zeros" step needed.
Version comparison is everywhere in infra tooling: deciding if an installed dependency satisfies a minimum-version constraint, checking whether a rolling deploy is going forward or backward between two release tags, or sorting a list of container image tags. All of them need exactly this "compare numerically, pad the shorter one with zeros" logic, and getting the leading-zero and different-length cases wrong is a common source of real bugs.
The problem guarantees every revision fits in a 32-bit integer, so a standard int is safe here. If a version scheme allowed arbitrarily large revision numbers, you'd want a bigger integer type (or a big-integer library) for the conversion step — the rest of the comparison logic wouldn't need to change.
Mainly avoiding the upfront cost of building two full lists of revisions when, in the common case, the very first revision already decides the answer (most version comparisons differ at the major or minor version, not deep in the patch number). It reads and compares one revision at a time and can return immediately, so on a real workload comparing many version pairs it does less unnecessary work on average, even though both approaches are O(n + m) in the worst case.