DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Compare Version Numbers

mediumStrings Must-do

Problem statement

A version string is a list of non-negative integer revisions joined by dots, such as 2.10.3. A revision may have leading zeros (04 is the same as 4).

Given two version strings version1 and version2, compare them revision by revision from left to right, treating each revision as an integer. If one version has fewer revisions, the missing ones count as 0, so 1.2 equals 1.2.0.0.

Return -1 if version1 is smaller, 1 if it is larger, and 0 if they are equal.

Examples

Example 1

Input: version1 = "2.10.3", version2 = "2.9.12"

Output: 1

Explanation: The first revisions tie at 2. Then 10 > 9, so version1 is newer. The third revision is never looked at.

Example 2

Input: version1 = "1.04", version2 = "1.4.0.0"

Output: 0

Explanation: 04 is 4, and the extra revisions in version2 are zeros.

Hints

Approach

Parse both strings in step, one revision at a time, without splitting.

  1. Keep a pointer i into version1 and j into version2.
  2. While either pointer is still inside its string:
    • read digits from version1 starting at i, building the number x = x * 10 + digit, until you hit a dot or the end. Skip the dot. If i was already past the end, x stays 0;
    • do the same for version2 to get y;
    • if x != y, return the comparison.
  3. Return 0.

Each character is read once and only two integers are held at a time, so memory use is constant.

ComplexityTime O(n + m)Space O(1)
Python
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
i, j, n, m = 0, 0, len(version1), len(version2)
while i < n or j < m:
x = 0
while i < n and version1[i] != ".":
x = x * 10 + int(version1[i])
i += 1
y = 0
while j < m and version2[j] != ".":
y = y * 10 + int(version2[j])
j += 1
if x != y:
return -1 if x < y else 1
i += 1 # step over the dot
j += 1
return 0

Follow-up questions

  • Sort a list of 10,000 version strings using your comparison.
  • Extend the comparison to support a pre-release suffix such as -rc2, which sorts before the final release.

Frequently asked questions

Deciding whether a host's agent, kernel or package is older than a required minimum is version comparison. Doing it with plain string comparison is a classic bug: it ranks 1.10 below 1.9 and skips an upgrade.

String.split takes a regular expression, and . means "any character". split(".") splits on everything and returns an empty array. Use split("\\.").

No. Semantic versioning adds pre-release and build labels like 1.4.0-rc.1, and a pre-release sorts before the plain release. This problem has only numeric revisions.