0369MediumTwo PointersString

Firmware Revision Order

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A device reports its firmware revision as a string: one or more chunks of decimal digits joined by single dots, for example "4.11.0".

A chunk is read as a plain decimal integer, so leading zeros inside a chunk carry no meaning and "3.04" names the same revision as "3.4".

Compare the revisions left and right. Line their chunks up starting from the leftmost one. When one revision runs out of chunks before the other, treat each of its missing chunks as 0.

Return -1 when left is the earlier revision, 1 when right is the earlier revision, and 0 when the two strings name the same revision.

Examples

Example 1

Input: left = "2.9", right = "2.10"
Output: -1

The first chunks tie at 2. The second chunks read as 9 and 10, and 9 is the smaller integer, so left is the earlier revision.

Example 2

Input: left = "7.012", right = "7.12"
Output: 0

The chunk "012" reads as the integer 12, matching "12", and the first chunks both read as 7, so the two strings name the same revision.

Example 3

Input: left = "5.0.1", right = "5"
Output: 1

Padding the right-hand revision gives chunks 5, 0 and 0. The first two pairs tie and the third pair is 1 against 0, so right is the earlier revision.

Example 4

Input: left = "3.0", right = "3"
Output: 0

The missing chunk on the right counts as 0, which matches the 0 on the left, so the revisions are the same.

Constraints

1 <= left.length, right.length <= 500
left and right contain only digits and '.'.
left and right are valid revision strings.
Every chunk in left and right fits in a 32-bit signed integer.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def compare_version(left: str, right: str) -> int:

Java

public int compareVersion(String left, String right)

The intended approach

Time O(len(left) + len(right))Space O(1)

Hold one cursor in each string and, on every round, read the digits up to the next dot into an integer, which discards leading zeros for free. A cursor sitting past the end of its string yields 0, which is exactly the padding rule. Compare the two chunk values as soon as both are in hand and return the moment they differ; if both cursors run out with every pair equal, the revisions match.

Pythonentry point: compare_version

def compare_version(left, right):
    # Two cursors walk the two strings once, reading one chunk at a time and
    # treating a cursor that has run off the end as chunk value 0.
    # Time O(len(left) + len(right)), space O(1).
    i, j = 0, 0
    n, m = len(left), len(right)
    while i < n or j < m:
        a = 0
        while i < n and left[i] != ".":
            a = a * 10 + (ord(left[i]) - 48)
            i += 1
        i += 1
        b = 0
        while j < m and right[j] != ".":
            b = b * 10 + (ord(right[j]) - 48)
            j += 1
        j += 1
        if a < b:
            return -1
        if a > b:
            return 1
    return 0

The obvious version

Split both strings on dots, convert every chunk to an integer, pad the shorter list with zeros, and compare the two integer lists element by element.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_compare_version(left, right):
    a = [int(chunk) for chunk in left.split(".")]
    b = [int(chunk) for chunk in right.split(".")]
    while len(a) < len(b):
        a.append(0)
    while len(b) < len(a):
        b.append(0)
    if a < b:
        return -1
    if a > b:
        return 1
    return 0

How this problem was checked

Reference solution executed against 13 test cases — 13 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in